#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, m, k;
int u[300021], v[300021];
ll c[300021], p[100001];
int cmp1[100001], cmp2[100001];
int find(int A, int *cmp) { return (A == cmp[A] ? A : cmp[A] = find(cmp[A], cmp)); }
void onion(int A, int B, int *cmp) { cmp[find(A, cmp)] = find(B, cmp); }
vector<int> compressed;
vector<pair<int, ll>> graph[100001];
int root;
vector<tuple<ll, int, int>> critical;
bool assign(int node, int dest, ll weight, int parent = 0) {
if (node == dest) return true;
bool good = false;
for (int i = 0; i < graph[node].size(); i++)
if (graph[node][i].first != parent) {
if (assign(graph[node][i].first, dest, weight, node)) {
good = true;
if (graph[node][i].second == -1)
graph[node][i].second = weight;
}
}
return good;
}
pair<ll, ll> calc(int node, int parent = 0) {
pair<ll, ll> ans = {0, p[node]};
for (pair<int, ll> i : graph[node]) if (i.first != parent) {
pair<ll, ll> tmp = calc(i.first, node);
ans.first += tmp.first + tmp.second * i.second;
ans.second += tmp.second;
}
return ans;
}
ll check(int mask) {
// Onion stuff based on mask, and construct some edges in the graph
for (int i = 1; i <= k; i++) if (mask & (1 << i - 1)) {
graph[find(u[m + i], cmp2)].push_back({find(v[m + i], cmp2), -1});
graph[find(v[m + i], cmp2)].push_back({find(u[m + i], cmp2), -1});
onion(u[m + i], v[m + i], cmp2);
}
for (auto i : critical) {
if (find(get<1>(i), cmp2) == find(get<2>(i), cmp2)) {
// Assign weights to edges on the path between these two nodes
assign(find(get<1>(i), cmp1), find(get<2>(i), cmp1), get<0>(i));
assign(find(get<2>(i), cmp1), find(get<1>(i), cmp1), get<0>(i));
} else {
// Add an edge to the graph
graph[find(get<1>(i), cmp2)].push_back({find(get<2>(i), cmp2), 0});
graph[find(get<2>(i), cmp2)].push_back({find(get<1>(i), cmp2), 0});
onion(get<1>(i), get<2>(i), cmp2);
}
}
pair<ll, ll> ans = calc(root);
// Reset the graph and the DSU
for (int i : compressed) graph[i].clear(), cmp2[i] = i;
return ans.first;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> c[i];
for (int i = 1; i <= k; i++) cin >> u[m + i] >> v[m + i];
for (int i = 1; i <= n; i++) cin >> p[i];
// Find the mandatory edges and collapse components together
vector<tuple<ll, int, int>> edges;
for (int i = 1; i <= m + k; i++) edges.push_back({c[i], u[i], v[i]});
sort(edges.begin(), edges.end());
iota(cmp1 + 1, cmp1 + n + 1, 1);
iota(cmp2 + 1, cmp2 + n + 1, 1);
for (auto i : edges) {
if (find(get<1>(i), cmp1) != find(get<2>(i), cmp1)) {
if (get<0>(i)) {
p[find(get<2>(i), cmp2)] += p[find(get<1>(i), cmp2)];
onion(get<1>(i), get<2>(i), cmp2);
}
onion(get<1>(i), get<2>(i), cmp1);
}
}
// Find the K + 1 component parents and the root after compression
for (int i = 1; i <= n; i++) {
cmp1[i] = cmp2[i];
if (i == cmp2[i]) compressed.push_back(i);
}
root = find(1, cmp2);
// Find the K "critical" edges
for (auto i : edges) {
if (get<0>(i) && find(get<1>(i), cmp1) != find(get<2>(i), cmp1)) {
critical.push_back(i);
onion(get<1>(i), get<2>(i), cmp1);
}
}
for (int i = 1; i <= n; i++) cmp1[i] = cmp2[i];
// Test each subset of edges
ll ans = 0;
for (int mask = 1; mask < (1 << k); mask++) ans = max(ans, check(mask));
cout << ans;
return 0;
}
Compilation message
toll.cpp: In function 'bool assign(int, int, ll, int)':
toll.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i = 0; i < graph[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'll check(int)':
toll.cpp:44:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
44 | for (int i = 1; i <= k; i++) if (mask & (1 << i - 1)) {
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
2668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
2668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
2668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
2668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
