#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define int long long int
const int N = 1e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;
class DisjointSets {
private:
vector<int> p, sz;
public:
DisjointSets(int n) : p(n), sz(n) {
for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1;}
}
int get(int u) {
return p[u] = (u == p[u] ? u : get(p[u]));
}
void init() {
for (int i = 0; i < (int) p.size(); i++) {
p[i] = i; sz[i] = 1;
}
}
bool unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v) {
return 0;
}
if (sz[u] < sz[v])
swap(u, v);
p[v] = u;
sz[u] += sz[v];
sz[v] = 0;
return 1;
}
};
int K = 21, root = 1;
vector<tuple<int, int>> bled(K);
vector<tuple<int, int, int>> sld;
vector<int> a(N), l(N), lvl(N), sub(N), up(N);
vector<vector<int>> g(N, vector<int> ());
void dfs(int u, int p) {
sub[u] = a[u];
up[u] = p;
for (auto v: g[u]) {
if (v != p) {
lvl[v] = lvl[u] + 1;
dfs(v, u);
sub[u] += sub[v];
}
}
}
void upd(int u, int v, int w) {
while (u != v) {
if (lvl[u] < lvl[v])
swap(u, v);
l[u] = min(l[u], w);
u = up[u];
}
}
int n, m, k;
int cnt = 1;
vector<tuple<int, int, int>> simplify(vector<tuple<int, int, int>> edges) {
DisjointSets dsu(n + 1);
for (int i = 0; i < k; i++) {
auto [u, v] = bled[i];
bool ok = dsu.unite(u, v);
}
vector<bool> state((int) edges.size());
for (int i = 0; i < (int) edges.size(); i++) {
auto [w, u, v] = edges[i];
state[i] = dsu.unite(u, v);
}
dsu.init();
for (int i = 0; i < (int) edges.size(); i++) {
auto [w, u, v] = edges[i];
if (state[i]) {
dsu.unite(u, v);
}
}
vector<int> nr(n + 1);
for (int i = 1; i <= n; i++) {
int g = dsu.get(i);
if (nr[g] > 0) continue;
nr[g] = cnt;
cnt++;
}
// 3 5
// 1 2
// 2 4
vector<tuple<int, int, int>> we;
for (int i = 0; i < (int) edges.size(); i++) {
auto [w, u, v] = edges[i];
if (!state[i]) {
we.push_back({w, nr[dsu.get(u)], nr[dsu.get(v)]});
}
}
for (int i = 0; i < k; i++) {
auto [u, v] = bled[i];
bled[i] = {nr[dsu.get(u)], nr[dsu.get(v)]};
}
vector<int> na(n + 1);
for (int i = 1; i <= n; i++)
na[nr[dsu.get(i)]] += a[i];
for (int i = 1; i < cnt; i++)
a[i] = na[i];
root = nr[dsu.get(1)];
return we;
}
int32_t main(int32_t argc, char *argv[]) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
cin >> n >> m >> k;
vector<tuple<int, int, int>> edges;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({w, u, v});
}
sort(edges.begin(), edges.end());
DisjointSets dsu(n + 1);
for (auto i: edges) {
auto [w, u, v] = i;
if (dsu.unite(u, v))
sld.push_back(i);
}
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
bled[i] = {x, y};
}
for (int i = 1; i <= n; i++)
cin >> a[i];
sld = simplify(sld);
int ans = 0;
DisjointSets dsu1(30);
for (int msk = 0; msk < (1 << k); msk++) {
dsu1.init();
for (int i = 1; i < cnt; i++)
g[i].clear(), l[i] = INF;
bool ok = 0;
for (int i = 0; i < k; i++)
if (((1 << i) & msk)) {
auto [u, v] = bled[i];
if (!(dsu1.unite(u, v))) {
ok = 1;
break;
}
g[u].push_back(v);
g[v].push_back(u);
}
if (ok) continue;
vector<bool> state(n + 1);
for (int i = 0; i < (int) sld.size(); i++) {
auto [w, u, v] = sld[i];
state[i] = dsu1.unite(u, v);
if (state[i]) {
g[u].push_back(v);
g[v].push_back(u);
}
}
dfs(root, -1);
for (int i = 0; i < (int) sld.size(); i++) {
if (!state[i]) {
auto [w, u, v] = sld[i];
upd(u, v, w);
}
}
int sm = 0;
for (int i = 0; i < k; i++)
if ((1 << i) & msk) {
auto [u, v] = bled[i];
if (lvl[u] > lvl[v])
swap(u, v);
sm += l[v] * sub[v];
}
ans = max(ans, sm);
}
cout << ans << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |