#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 3e5 + 7, K = 23, INF = 1e9 + 7;
struct Edge { int u, v, c; bool in; };
bool comp(Edge a, Edge b) { return a.c < b.c; }
int root(int u, int *par) {
if (par[u] == u) return u;
else return par[u] = root(par[u], par);
}
int par[N], par1[N], w[N], num[N], ww[K];
int n, m, k;
bool in[N];
int small_par[K];
vector <pair <int, bool> > g[K];
int tree_par[K];
int h[K], cnt[K], up[K];
void dfs(int u, int p) {
tree_par[u] = p;
cnt[u] = ww[u];
for (auto e : g[u]) {
int v = e.f;
if (v != p) {
//cout << "go " << u << ' ' << e.f << ' ' << e.s << endl;
h[v] = h[u] + 1;
if (e.s)
up[v] = INF;
else
up[v] = 0;
dfs(v, u);
cnt[u] += cnt[v];
}
}
}
void getup(int &u, int c) {
up[u] = min(up[u], c);
u = tree_par[u];
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
#define endl '\n'
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> m >> k;
vector <Edge> ev;
for (int i = 0; i < m; ++i) {
int u, v, c; cin >> u >> v >> c;
ev.app({u, v, c, 0});
}
sort(all(ev), comp);
for (int i = 1; i <= n; ++i) par[i] = i;
for (auto &e : ev) {
if (root(e.u, par) != root(e.v, par)) {
e.in = 1;
par[root(e.u, par)] = root(e.v, par);
}
}
for (int i = 1; i <= n; ++i) par[i] = par1[i] = i;
vector <ii> add;
for (int i = 0; i < k; ++i) {
int u, v; cin >> u >> v;
add.app(mp(u, v));
if (root(u, par) != root(v, par))
par[root(u, par)] = root(v, par);
}
vector <Edge> small;
for (auto &e : ev) {
if (root(e.u, par) != root(e.v, par)) {
par[root(e.u, par)] = root(e.v, par);
par1[root(e.u, par1)] = root(e.v, par1);
}
else if (e.in)
small.app(e);
}
int ptr = 0;
for (int i = 1; i <= n; ++i)
if (par1[i] == i)
num[i] = ++ptr;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
ww[num[root(i, par1)]] += w[i];
}
int troot = num[root(1, par1)];
sort(all(small), comp);
for (auto &e : small) {
e.u = num[root(e.u, par1)];
e.v = num[root(e.v, par1)];
}
for (auto &e : add) {
e.f = num[root(e.f, par1)];
e.s = num[root(e.s, par1)];
}
int ans = 0;
for (int mask = 0; mask < (1 << k); ++mask) {
for (int i = 0; i < K; ++i) {
small_par[i] = i;
g[i].clear();
}
bool cyc = 0;
for (int i = 0; i < k; ++i)
if ((mask >> i) & 1) {
int u = add[i].f, v = add[i].s;
if (root(u, small_par) == root(v, small_par)) {
cyc = 1;
break;
}
small_par[root(u, small_par)] = root(v, small_par);
g[u].app({v, 1}); g[v].app({u, 1});
//cout << "edge " << u << ' ' << v << ' ' << 1 << endl;
}
if (cyc)
continue;
vector <Edge> rel;
for (auto e : small) {
if (root(e.u, small_par) == root(e.v, small_par))
rel.app(e);
else {
small_par[root(e.u, small_par)] = root(e.v, small_par);
g[e.u].app({e.v, 0}); g[e.v].app({e.u, 0});
//cout << "edge " << e.u << ' ' << e.v << ' ' << 0 << endl;
}
}
dfs(troot, troot);
/*
cout << "up : ";
for (int i = 1; i <= ptr; ++i)
cout << up[i] << ' ';
cout << endl;
*/
for (auto e : rel) {
int u = e.u, v = e.v;
while (h[u] > h[v])
getup(u, e.c);
while (h[v] > h[u])
getup(v, e.c);
while (u != v) {
getup(u, e.c);
getup(v, e.c);
}
}
//cout << "mask " << mask << endl;
int nn = 0;
for (int i = 1; i <= ptr; ++i)
if (i != troot) {
//cout << i << ' ' << cnt[i] << ' ' << up[i] << endl;
nn += cnt[i] * up[i];
}
ans = max(ans, nn);
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
384 KB |
Output is correct |
| 5 |
Correct |
8 ms |
768 KB |
Output is correct |
| 6 |
Correct |
8 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
384 KB |
Output is correct |
| 5 |
Correct |
8 ms |
768 KB |
Output is correct |
| 6 |
Correct |
8 ms |
768 KB |
Output is correct |
| 7 |
Correct |
268 ms |
22200 KB |
Output is correct |
| 8 |
Correct |
300 ms |
22312 KB |
Output is correct |
| 9 |
Correct |
272 ms |
22100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
384 KB |
Output is correct |
| 5 |
Correct |
8 ms |
768 KB |
Output is correct |
| 6 |
Correct |
8 ms |
768 KB |
Output is correct |
| 7 |
Correct |
268 ms |
22200 KB |
Output is correct |
| 8 |
Correct |
300 ms |
22312 KB |
Output is correct |
| 9 |
Correct |
272 ms |
22100 KB |
Output is correct |
| 10 |
Correct |
1777 ms |
22100 KB |
Output is correct |
| 11 |
Correct |
2041 ms |
22100 KB |
Output is correct |
| 12 |
Correct |
2040 ms |
22268 KB |
Output is correct |
