#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#include <set>
#include <functional>
using namespace std;
struct DSU
{
int N;
vector<int> A;
DSU(int _N = 0): N(_N), A(_N + 1, -1) {};
void reset(int _N) { N = _N, A.assign(N + 1, -1); }
int get(int u) { return A[u] < 0 ? u : A[u] = get(A[u]); }
bool same(int u, int v) { return get(u) == get(v); }
void join(int u, int v)
{
u = get(u), v = get(v);
if (u == v) return;
if (A[u] > A[v]) swap(u, v);
A[u] += A[v], A[v] = u;
}
};
const int MAXN = 100007, MAXM = 300007, MAXK = 20, INF = 1e8;
int N, M, K, C;
int label[MAXN], P[MAXN];
int U[MAXM], V[MAXM], W[MAXM], flag[MAXN];
int X[MAXK], Y[MAXK], Z[MAXK];
int64_t weight[MAXN], subtree[MAXN];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> K;
for (int e = 0; e < M; ++e) cin >> U[e] >> V[e] >> W[e];
for (int i = 0; i < K; ++i) cin >> X[i] >> Y[i];
for (int i = 1; i <= N; ++i) cin >> P[i];
vector<int> lis(M);
iota(lis.begin(), lis.end(), 0);
sort(lis.begin(), lis.end(), [&](int i, int j) { return W[i] < W[j]; });
DSU dsu(N);
for (int i = 0; i < K; ++i) dsu.join(X[i], Y[i]);
for (auto &e : lis) if (!dsu.same(U[e], V[e])) dsu.join(U[e], V[e]), flag[e] = true;
dsu.reset(N);
for (auto &e : lis) if (flag[e]) dsu.join(U[e], V[e]);
map<int, int> convert;
for (int u = 1; u <= N; ++u) {
int cur = dsu.get(u);
if (convert.find(cur) == convert.end()) convert[cur] = ++C;
label[u] = convert[cur];
weight[label[u]] += P[u];
}
for (int e = 0; e < M; ++e) U[e] = label[U[e]], V[e] = label[V[e]];
for (int i = 0; i < K; ++i) X[i] = label[X[i]], Y[i] = label[Y[i]];
vector<int> addIDs;
dsu.reset(C);
for (int e = 0; e < M; ++e) if (!dsu.same(U[e], V[e])) dsu.join(U[e], V[e]), addIDs.push_back(e);
vector<vector<pair<int, int>>> updates, tree;
function<set<pair<int, int>>(int, int, int64_t&)> dfs = [&](int u, int p, int64_t& ans) {
subtree[u] = weight[u];
set<pair<int, int>> curSet(updates[u].begin(), updates[u].end());
// for (auto upd : updates) curSet.insert(upd);
for (auto e : tree[u]) {
int v = e.first, spec = e.second;
if (v == p) continue;
auto tmpSet = dfs(v, u, ans);
if (spec) {
assert(!tmpSet.empty());
ans += tmpSet.begin()->first * subtree[v];
}
for (auto upd : tmpSet) {
if (curSet.find(upd) == curSet.end()) curSet.insert(upd);
else curSet.erase(upd);
}
subtree[u] += subtree[v];
}
return curSet;
};
int64_t ans = -1;
for (int mask = 0; mask < (1 << K); ++mask) {
tree.assign(C + 1, vector<pair<int, int>>(0));
updates.assign(C + 1, vector<pair<int, int>>(0));
bool cycle = false;
dsu.reset(C);
for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
if (dsu.same(X[i], Y[i])) { cycle = true; break; }
else { dsu.join(X[i], Y[i]), tree[X[i]].emplace_back(Y[i], true), tree[Y[i]].emplace_back(X[i], true); }
}
if (cycle) continue;
for (int e : addIDs) {
if (!dsu.same(U[e], V[e])) {
dsu.join(U[e], V[e]), tree[U[e]].emplace_back(V[e], false), tree[V[e]].emplace_back(U[e], false);
} else {
updates[U[e]].emplace_back(W[e], e);
updates[V[e]].emplace_back(W[e], e);
}
}
int64_t curAns = 0;
dfs(1, 0, curAns);
ans = max(ans, curAns);
}
cout << ans << endl;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:44:2: error: 'iota' was not declared in this scope
iota(lis.begin(), lis.end(), 0);
^~~~
toll.cpp:44:2: note: suggested alternative: 'int'
iota(lis.begin(), lis.end(), 0);
^~~~
int
