#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=1e5, mxK=20, mxM=3e5;
int n, k, m, r[mxN], p[mxK+1], d[mxK+1], rs, w[mxK+1];
array<int, 3> e[mxM];
array<int, 2> a[mxK];
vector<int> adj[mxN], b;
ll s[mxK+1], ans;
struct n1 {
int r;
n1 operator+(const n1 &o) const {
return r^o.r?n1{max(r, o.r)}:n1{r+1};
}
bool operator<(const n1 &o) const {
return r<o.r;
}
};
struct n2 {
int r, a;
n2 operator+(const n2 &o) const {
return r^o.r?n2{max(r, o.r), a}:n2{r+1 ,a};
}
bool operator<(const n2 &o) const {
return r<o.r;
}
};
template<size_t S, class T>
struct dsu {
int p[S];
T a[S];
int find(int x) {
return x==p[x]?x:(p[x]=find(p[x]));
}
bool join(int x, int y) {
if((x=find(x))==(y=find(y)))
return 0;
a[x]=a[x]+a[y];
if(a[x]<a[y])
swap(x, y);
p[y]=x;
return 1;
}
};
dsu<mxN, n1> d1, d2, d3;
dsu<mxK+1, n1> d4;
dsu<mxK+1, n2> d5;
void dfs1(int u, int pu=-1) {
p[u]=pu;
d[u]=pu^-1?d[pu]+1:0;
for(int v : adj[u])
if(v!=pu)
dfs1(v, u);
}
ll dfs2(int u, ll d=0) {
ll r=d*s[u];
for(int v : adj[u])
if(v!=p[u])
r+=dfs2(v, d+w[v]);
return r;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for(int i=0; i<m; ++i)
cin >> e[i][1] >> e[i][2] >> e[i][0], --e[i][1], --e[i][2];
sort(e, e+m);
iota(d1.p, d1.p+n, 0);
for(int i=0; i<k; ++i) {
cin >> a[i][0] >> a[i][1], --a[i][0], --a[i][1];
d1.join(a[i][0], a[i][1]);
}
iota(d2.p, d2.p+n, 0);
iota(d3.p, d3.p+n, 0);
for(int i=0; i<m; ++i) {
if(!d2.join(e[i][1], e[i][2]))
continue;
if(d1.join(e[i][1], e[i][2]))
d3.join(e[i][1], e[i][2]);
else
b.push_back(i);
}
for(int i=0; i<n; ++i)
if(d3.find(i)==i)
r[i]=rs++;
for(int i=0, si; i<n; ++i) {
cin >> si;
s[r[d3.find(i)]]+=si;
}
for(int bi : b) {
e[bi][1]=r[e[bi][1]];
e[bi][2]=r[e[bi][2]];
}
for(int i=0; i<k; ++i) {
a[i][0]=r[a[i][0]];
a[i][1]=r[a[i][1]];
}
for(int i=0; i<1<<k; ++i) {
for(int j=0; j<rs; ++j) {
adj[j].clear();
d5.a[j]={0, j};
}
iota(d4.p, d4.p+rs, 0);
memset(d4.a, 0, sizeof(d4.a));
iota(d5.p, d5.p+rs, 0);
for(int j=0; j<k; ++j) {
if(i>>j&1&&d4.join(a[j][0], a[j][1])) {
adj[a[j][0]].push_back(a[j][1]);
adj[a[j][1]].push_back(a[j][0]);
}
}
deque<array<int, 3>> c;
for(int bi : b) {
if(d4.join(e[bi][1], e[bi][2])) {
adj[e[bi][1]].push_back(e[bi][2]);
adj[e[bi][2]].push_back(e[bi][1]);
c.push_front({0, e[bi][1], e[bi][2]});
} else
c.push_back(e[bi]);
}
dfs1(r[d3.find(0)]);
for(array<int, 3> ci : c) {
int u=d5.a[d5.find(ci[1])].a, v=d5.a[d5.find(ci[2])].a;
while(u^v) {
if(d[u]<d[v])
swap(u, v);
w[u]=ci[0];
assert(d5.join(p[u], u));
u=d5.a[d5.find(u)].a;
}
}
ans=max(dfs2(r[d3.find(0)]), ans);
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
