#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int numCosts;
class Edge{
public:
int s, e, c;
bool og;
Edge(int a, int b, int d){
s = a;
e = b;
c = d;
}
bool operator<(const Edge &o) const{
return c<o.c;
}
};
vector<Edge> options[20];
int use[20];
vector<Edge> used;
long long ans;
vector<Edge> adj[100000];
vector<int> freq;
pair<long long, long long> go2(int now, int from){
pair<long long, long long> ret = make_pair(freq[now],0LL);
for(int i = 0; i<adj[now].size(); i++){
Edge ed = adj[now][i];
if(ed.e==from){
continue;
}
pair<long long, long long> got = go2(ed.e,now);
//first sub, second ans
ret.second += got.second + (long long)got.first*(long long)ed.c;
ret.first += got.first;
}
return ret;
}
void go(int now){
if(now==numCosts){
for(int i = 0; i<used.size(); i++){
adj[used[i].s].push_back(Edge(0,used[i].e,0));
adj[used[i].e].push_back(Edge(0,used[i].s,0));
}
for(int i = 0; i<numCosts; i++){
Edge ed = options[i][use[i]];
adj[ed.s].push_back(Edge(0,ed.e,ed.c));
adj[ed.e].push_back(Edge(0,ed.s,ed.c));
}
// for(int i = 0; i<n; i++){
// cout << i << ":";
// for(int j = 0; j<adj[i].size(); j++){
// cout << " " << adj[i][j].e;
// }
// cout << endl;
// }
ans = max(ans,go2(0,-1).second);
for(int i = 0; i<n; i++){
adj[i].clear();
}
}
else{
for(int i = 0; i<options[now].size(); i++){
use[now] = i;
go(now+1);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
vector<Edge> edges;
for(int i = 0; i<m; i++){
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
edges.push_back(Edge(a,b,c));
}
sort(edges.begin(),edges.end());
vector<Edge> other;
bool assigned[k];
for(int i = 0; i<k; i++){
int a, b;
cin >> a >> b;
a--;
b--;
assigned[i] = false;
other.push_back(Edge(a,b,-1));
}
int comp[n];
int sz[n];
vector<int> li[n];
for(int i = 0; i<n; i++){
comp[i] = i;
sz[i] = 1;
li[i].push_back(i);
}
for(int i = 0; i<m; i++){
int ca = comp[edges[i].s];
int cb = comp[edges[i].e];
if(ca==cb){
continue;
}
if(sz[ca]>sz[cb]){
swap(ca,cb);
}
//ca < cb
sz[cb] += sz[ca];
for(int j = 0; j<li[ca].size(); j++){
comp[li[ca][j]] = cb;
li[cb].push_back(li[ca][j]);
}
li[ca].clear();
bool any = false;
for(int j = 0; j<k; j++){
if(!assigned[j] && comp[other[j].s]==comp[other[j].e]){
assigned[j] = true;
any = true;
other[j].og = false;
other[j].c = edges[i].c;
}
}
if(!any){
used.push_back(edges[i]);
}
else{
edges[i].og = true;
other.push_back(edges[i]);
}
}
for(int i = 0; i<k; i++){
assert(assigned[i]);
}
sort(other.begin(),other.end());
vector<int> costs;
numCosts = 0;
for(int i = 0; i<other.size(); i++){
if(i==0 || costs[costs.size()-1]!=other[i].c){
costs.push_back(other[i].c);
numCosts++;
}
if(other[i].og){
other[i].c = 0;
}
options[numCosts-1].push_back(other[i]);
}
for(int i = 0; i<n; i++){
int x;
cin >> x;
freq.push_back(x);
}
ans = 0LL;
go(0);
cout << ans << endl;
return 0;
}
Compilation message
toll.cpp: In function 'std::pair<long long int, long long int> go2(int, int)':
toll.cpp:26:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
^
toll.cpp: In function 'void go(int)':
toll.cpp:40:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<used.size(); i++){
^
toll.cpp:62:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<options[now].size(); i++){
^
toll.cpp: In function 'int main()':
toll.cpp:110:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<li[ca].size(); j++){
^
toll.cpp:138:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<other.size(); i++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2856 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2856 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2856 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2856 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
