#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 2000000000
const int N = 1010;
int n , m , k , prnt[N] , cur[N];
long long current = 0 , comp[N];
vector< pair< pair<int,int> , pair<int,int> > > v,ed2;
vector< vector< pair<int, pair<int,int> > > > g;
pair<int,int> ed[30];
int Find(int u){
if(u == prnt[u]) return u;
return prnt[u] = Find(prnt[u]);
}
void min_tree(vector< pair< pair<int,int> ,pair<int,int> > > v, vector < vector< pair<int, pair<int,int> > > > &g,bool b){
g.clear();
g.resize(n+1);
sort(v.begin(),v.end());
for(int i=1;i<=n;i++) prnt[i] = i;
for(int i=0;i<v.size();i++){
int a = Find(prnt[v[i].second.first]);
int b = Find(prnt[v[i].second.second]);
if(a == b) continue;
prnt[a] = b;
g[v[i].second.first].push_back(make_pair(v[i].second.second,v[i].first));
g[v[i].second.second].push_back(make_pair(v[i].second.first,v[i].first));
if(b)
ed2.push_back(v[i]);
}
}
void DFS2(int node,int prnt,int num){
comp[node] = num;
for(int i=0;i<g[node].size();i++){
if(g[node][i].first != prnt) DFS2(g[node][i].first,node,num);
}
}
long long get(int node,int node2){
DFS2(node2,node,1);
long long mn = oo;
for(int i=0;i<ed2.size();i++){
if(ed2[i].first.first == 0) continue;
if(comp[ed2[i].second.first] == comp[ed2[i].second.second]) continue;
mn = min(mn,(long long)ed2[i].first.first);
}
DFS2(node2,node,0);
return mn;
}
long long DFS(int node,int prnt){
long long all = 0 ;
for(int i=0;i<g[node].size();i++){
if(g[node][i].first == prnt) continue;
long long res = DFS(g[node][i].first,node);
if(g[node][i].second.second){
current += res * get(node,g[node][i].first);
}
all += res;
}
return all + cur[node];
}
int main() {
//freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) prnt[i] = i ;
for(int i=0;i<m;i++){
int u ,V , c;
scanf("%d%d%d",&u,&V,&c);
v.push_back(make_pair(make_pair(c,0),make_pair(u,V)));
}
min_tree(v,g,1);
for(int i=0;i<k;i++){
scanf("%d%d",&ed[i].first,&ed[i].second);
}
for(int i=1;i<=n;i++)
scanf("%d",&cur[i]);
long long ans = 0 ;
for(int i=0;i<(1 << k);i++){
for(int j=0;j<k;j++){
if((i >> j & 1) == 1) ed2.push_back(make_pair(make_pair(0,1),ed[j]));
}
min_tree(ed2,g,0);
current = 0 ;
DFS(1,-1);
ans = max(ans,current);
for(int j=0;j<k;j++){
if((i >> j & 1) == 1) ed2.pop_back();
}
}
cout << ans << endl;
return 0;
}
Compilation message
toll.cpp: In function 'void min_tree(std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >, std::vector<std::vector<std::pair<int, std::pair<int, int> > > >&, bool)':
toll.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++){
^
toll.cpp: In function 'void DFS2(int, int, int)':
toll.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[node].size();i++){
^
toll.cpp: In function 'long long int get(int, int)':
toll.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed2.size();i++){
^
toll.cpp: In function 'long long int DFS(int, int)':
toll.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[node].size();i++){
^
toll.cpp: In function 'int main()':
toll.cpp:68:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&m,&k);
^
toll.cpp:72:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&u,&V,&c);
^
toll.cpp:77:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&ed[i].first,&ed[i].second);
^
toll.cpp:80:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&cur[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 3 |
Incorrect |
1279 ms |
3292 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 3 |
Incorrect |
1279 ms |
3292 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 3 |
Incorrect |
1279 ms |
3292 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2036 KB |
Output is correct |
| 3 |
Incorrect |
1279 ms |
3292 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
