#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int in() {
int result = 0;
char ch = getchar_unlocked();
while (true) {
if(ch >= '0' && ch <= '9')
break;
ch = getchar_unlocked();
}
result = ch-'0';
while(true) {
ch = getchar_unlocked();
if (ch < '0' || ch > '9')
break;
result = result*10 + (ch - '0');
}
return result;
}
inline void out(ll x) {
ll rev=x;
int count = 0;
if(x == 0) {
putchar_unlocked('0');
return;
}
while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
rev = 0;
while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
while(count--)
putchar_unlocked('0');
}
const int N = 100003, M = 300003, K = 23;
struct Enode {
int u, v, e;
bool operator < (const Enode &AA) const {
return e < AA.e;
}
} G[M], A[K], New[M], MN[K];
int p[N], Gtot = 0, n, m, k, fa[N], fa2[N], Atot = 0, Newtot = 0, MNtot = 0, tot = 0, remark[N];
ll sp[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int find2(int x) {return x == fa2[x] ? x : fa2[x] = find2(fa2[x]);}
ll sum[K];
bool used[K], mark[K];
struct node {int nxt, to, w;} E[K * K << 1];
int cnt, point[K], deep[K], fadis[K];
void ins(int u, int v, int w) {E[++cnt] = (node) {point[u], v, w}; point[u] = cnt;}
void dfs(int x) {
sum[x] = sp[x];
for (int i = point[x]; i; i = E[i].nxt)
if (E[i].to != fa[x]) {
fa[E[i].to] = x;
fadis[E[i].to] = E[i].w;
deep[E[i].to] = deep[x] + 1;
if (E[i].w == 0x7fffffff) mark[E[i].to] = true;
else mark[E[i].to] = false;
dfs(E[i].to);
sum[x] += sum[E[i].to];
}
}
void minit(int u, int v, int e) {
if (deep[u] < deep[v]) u ^= v ^= u ^= v;
while (deep[u] > deep[v]) {
if (mark[u] && fadis[u] > e)
fadis[u] = e;
u = fa[u];
}
if (u == v) return;
while (u != v) {
if (mark[u] && fadis[u] > e)
fadis[u] = e;
if (mark[v] && fadis[v] > e)
fadis[v] = e;
u = fa[u]; v = fa[v];
}
}
int main() {
n=in(), m=in(), k=in();
int u, v, e, etot = 0;
for (int i = 1; i <= m; ++i) {
u=in(), v=in(), e=in();
G[++Gtot] = (Enode) {u, v, e};
}
stable_sort(G + 1, G + Gtot + 1);
for (int i = 1; i <= n; ++i) fa[i] = fa2[i] = i;
for (int i = 1; i <= k; ++i) {
u=in(), v=in();
A[++Atot] = (Enode) {u, v, 0};
u = find(u); v = find(v);
if (u != v) fa[u] = v, ++etot;
}
for (int i = 1; i <= n; ++i) p[i]=in();
for (int i = 1; i <= Gtot; ++i) {
u = find(G[i].u); v = find(G[i].v);
if (u != v) {
++etot;
fa[u] = v;
u = find2(G[i].u); v = find2(G[i].v);
if (u != v) fa2[u] = v;
if (etot == n - 1) break;
}
}
for (int i = 1; i <= n; ++i) {
if (!remark[find2(i)])
remark[fa2[i]] = ++tot;
remark[i] = remark[fa2[i]];
}
for (int i = 1; i <= n; ++i) sp[remark[i]] += p[i];
for (int i = 1; i <= m; ++i) {
u = remark[G[i].u]; v = remark[G[i].v];
if (u != v)
New[++Newtot] = (Enode) {u, v, G[i].e};
}
stable_sort(New + 1, New + Newtot + 1);
for (int i = 1; i <= k; ++i) A[i].u = remark[A[i].u], A[i].v = remark[A[i].v];
etot = 0;
for (int i = 1; i <= tot; ++i) fa[i] = i;
for (int i = 1; i <= Newtot; ++i) {
u = find(New[i].u); v = find(New[i].v);
if (u != v) {
fa[u] = v;
++etot;
MN[++MNtot] = New[i];
if (etot == tot - 1) break;
}
}
int S = (1 << k); ll ans = 0;
for (int s = 1; s < S; ++s) {
for (int i = 1; i <= tot; ++i) fa[i] = i, point[i] = 0;
cnt = etot = 0;
for (int i = 0; i < k; ++i)
if ((s >> i) & 1) {
u = A[i + 1].u; v = A[i + 1].v;
if (find(u) != find(v)) {
fa[fa[u]] = fa[v];
++etot;
ins(u, v, 0x7fffffff);
ins(v, u, 0x7fffffff);
}
}
for (int i = 1; i <= MNtot; ++i) used[i] = false;
if (etot < tot - 1) {
for (int i = 1; i <= MNtot; ++i) {
u = find(MN[i].u); v = find(MN[i].v);
if (u != v) {
used[i] = true;
++etot;
fa[u] = v;
ins(MN[i].u, MN[i].v, MN[i].e);
ins(MN[i].v, MN[i].u, MN[i].e);
if (etot == tot - 1) break;
}
}
}
fa[remark[1]] = 0; dfs(remark[1]);
for (int i = 1; i <= MNtot; ++i)
if (!used[i])
minit(MN[i].u, MN[i].v, MN[i].e);
ll ret = 0;
for (int i = 1; i <= tot; ++i)
if (mark[i])
ret += sum[i] * fadis[i];
if (ret > ans) ans = ret;
}
out(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
440 KB |
Output is correct |
| 3 |
Correct |
2 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
440 KB |
Output is correct |
| 3 |
Correct |
2 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
448 KB |
Output is correct |
| 5 |
Correct |
3 ms |
748 KB |
Output is correct |
| 6 |
Correct |
3 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
440 KB |
Output is correct |
| 3 |
Correct |
2 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
448 KB |
Output is correct |
| 5 |
Correct |
3 ms |
748 KB |
Output is correct |
| 6 |
Correct |
3 ms |
748 KB |
Output is correct |
| 7 |
Correct |
104 ms |
6068 KB |
Output is correct |
| 8 |
Correct |
115 ms |
8248 KB |
Output is correct |
| 9 |
Correct |
113 ms |
8248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
440 KB |
Output is correct |
| 3 |
Correct |
2 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
448 KB |
Output is correct |
| 5 |
Correct |
3 ms |
748 KB |
Output is correct |
| 6 |
Correct |
3 ms |
748 KB |
Output is correct |
| 7 |
Correct |
104 ms |
6068 KB |
Output is correct |
| 8 |
Correct |
115 ms |
8248 KB |
Output is correct |
| 9 |
Correct |
113 ms |
8248 KB |
Output is correct |
| 10 |
Correct |
918 ms |
8248 KB |
Output is correct |
| 11 |
Correct |
1339 ms |
8248 KB |
Output is correct |
| 12 |
Correct |
1346 ms |
8248 KB |
Output is correct |
