#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr i64 inf = 1ll << 60;
#define rep(i, n) for (int i = 0; i < (n); ++i)
template <typename t> void chmax(t &a, const t b) {
if (a < b) a = b;
}
template <typename t> void chmin(t &a, const t b) {
if (a > b) a = b;
}
struct unionfind {
int n;
vector<int> data;
unionfind(const int n_) : n(n_), data(n, -1) {}
int find(int v) {
if (data[v] < 0)
return v;
else
return data[v] = find(data[v]);
}
int is_same(int a, int b) { return find(a) == find(b); }
int size(int v) { return -data[find(v)]; }
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (size(a) < size(b)) swap(a, b);
data[a] += data[b];
data[b] = a;
}
};
struct merger {
int n;
vector<int> roots;
vector<vector<int>> vals;
merger(const int n_) {
n = n_;
roots.assign(n, -1);
rep(i, n) vals.push_back({i});
}
int find(int a) {
if (roots[a] < 0)
return a;
else
return roots[a] = find(roots[a]);
}
int size(int v) { return -roots[find(v)]; }
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (size(a) < size(b)) swap(a, b);
for (const int e : vals[b]) vals[a].push_back(e);
roots[a] += roots[b];
roots[b] = a;
}
};
struct edge {
i64 cost;
int a;
int b;
};
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<edge> e(m);
rep(i, m) {
cin >> e[i].a >> e[i].b >> e[i].cost;
--e[i].a, --e[i].b;
}
vector<pair<int, int>> a(k);
for (auto &[x, y] : a) {
cin >> x >> y;
--x, --y;
}
vector<i64> p(n);
for (auto &e : p) cin >> e;
sort(e.begin(), e.end(), [](edge a, edge b) { return a.cost < b.cost; });
{
unionfind uft(n);
rep(i, k) uft.unite(a[i].first, a[i].second);
merger mt(n);
for (const auto &[cost, a, b] : e) {
if (uft.is_same(a, b)) continue;
uft.unite(a, b);
mt.merge(a, b);
}
vector<bool> used(n);
vector<vector<int>> groups;
rep(i, n) {
if (used[mt.find(i)]) continue;
used[mt.find(i)] = true;
groups.push_back(mt.vals[mt.find(i)]);
}
const int l = (int)size(groups);
for (auto &g : groups) sort(g.begin(), g.end());
sort(groups.begin(), groups.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
vector<int> att(n);
rep(i, l) {
const auto &g = groups[i];
for (const int e : g) att[e] = i;
}
vector<i64> np(l);
rep(i, n) np[att[i]] += p[i];
p = move(np);
for (auto &[x, y] : a) {
x = att[x];
y = att[y];
}
rep(i, m) {
e[i].a = att[e[i].a];
e[i].b = att[e[i].b];
}
vector<edge> e2;
for (const auto &[cost, a, b] : e)
if (a != b) e2.push_back({cost, a, b});
e = e2;
e2.clear();
uft = unionfind(l);
for (const auto &[cost, a, b] : e) {
if (uft.is_same(a, b)) continue;
uft.unite(a, b);
e2.push_back({cost, a, b});
}
e = move(e2);
n = l;
m = (int)size(e);
}
i64 ans = 0;
unionfind uftb(n);
vector<vector<pair<int, int>>> tree(n);
vector<i64> nec(n);
rep(bit, 1 << k) {
rep(i, n) tree[i].clear();
auto uft = uftb;
fill(nec.begin(),nec.end(),inf);
bool possible = true;
rep(i, k) {
if (bit & (1 << i)) {
if (uft.is_same(a[i].first, a[i].second)) {
possible = false;
break;
}
uft.unite(a[i].first, a[i].second);
tree[a[i].first].emplace_back(a[i].second, i);
tree[a[i].second].emplace_back(a[i].first, i);
}
}
if (not possible) continue;
rep(i, m) {
if (uft.is_same(e[i].a, e[i].b)) {
auto dfs = [&](auto &&self, const int v, const int p) -> bool {
for (auto &[t, c] : tree[v]) {
if (t == p) continue;
if (t == e[i].b) {
chmin(nec[c], e[i].cost);
return true;
}
if (self(self, t, v)) {
chmin(nec[c], e[i].cost);
return true;
}
}
return false;
};
assert(dfs(dfs, e[i].a, -1));
} else {
uft.unite(e[i].a, e[i].b);
tree[e[i].a].emplace_back(e[i].b, -1);
tree[e[i].b].emplace_back(e[i].a, -1);
}
}
i64 res = 0;
auto dfs = [&](auto &&self, const int v, const int p) -> i64 {
i64 sum = 0;
for (const auto &[t, c] : tree[v]) {
if (t == p) continue;
const i64 e = self(self, t, v);
if (c != -1) res += nec[c] * e;
sum += e;
}
return sum + p[v];
};
dfs(dfs, 0, -1);
chmax(ans, res);
}
cout << ans << endl;
}
Compilation message
toll.cpp: In lambda function:
toll.cpp:201:27: error: invalid types 'const int[const int]' for array subscript
201 | return sum + p[v];
| ^
