/**
* author: wxhtzdy
* created: 01.07.2022 13:03:09
**/
#include <bits/stdc++.h>
using namespace std;
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> a(m), b(m), c(m);
for (int i = 0; i < m; i++) {
cin >> a[i] >> b[i] >> c[i];
--a[i]; --b[i];
}
vector<int> x(k), y(k);
for (int i = 0; i < k; i++) {
cin >> x[i] >> y[i];
--x[i]; --y[i];
}
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
vector<vector<pair<int, int>>> g(n);
dsu d(n);
for (int i = 0; i < k; i++) {
d.unite(x[i], y[i]);
}
vector<array<int, 3>> e;
for (int i = 0; i < m; i++) {
if (d.unite(a[i], b[i])) {
g[a[i]].emplace_back(b[i], c[i]);
g[b[i]].emplace_back(a[i], c[i]);
} else {
e.push_back({a[i], b[i], c[i]});
}
}
int cc = 0;
vector<int> comp(n, -1);
vector<long long> f(n);
function<void(int, int)> Dfs = [&](int v, int id) {
comp[v] = id;
f[id] += p[v];
for (auto& p : g[v]) {
if (comp[p.first] == -1) {
Dfs(p.first, id);
}
}
};
for (int i = 0; i < n; i++) {
if (comp[i] == -1) {
Dfs(i, cc);
cc += 1;
}
}
for (int i = 0; i < k; i++) {
x[i] = comp[x[i]];
y[i] = comp[y[i]];
}
for (auto& p : e) {
p[0] = comp[p[0]];
p[1] = comp[p[1]];
}
long long ans = 0;
d.p.resize(cc);
g.resize(cc);
for (int s = 1; s < (1 << k); s++) {
for (int i = 0; i < cc; i++) {
d.p[i] = i;
}
bool ok = true;
for (int i = 0; i < k; i++) {
if (s >> i & 1) {
if (!d.unite(x[i], y[i])) {
ok = false;
}
}
}
if (!ok) {
continue;
}
for (int i = 0; i < cc; i++) {
g[i].clear();
}
for (int i = 0; i < k; i++) {
if (s >> i & 1) {
g[x[i]].emplace_back(y[i], 1);
g[y[i]].emplace_back(x[i], 1);
}
}
vector<array<int, 3>> q;
for (auto& p : e) {
if (!d.unite(p[0], p[1])) {
q.push_back(p);
} else {
g[p[0]].emplace_back(p[1], 0);
g[p[1]].emplace_back(p[0], 0);
}
}
vector<long long> fs(cc);
vector<bool> spec(cc);
vector<int> dep(cc);
vector<int> par(cc);
Dfs = [&](int v, int pr) {
fs[v] = f[v];
dep[v] = dep[pr] + 1;
par[v] = pr;
for (auto& p : g[v]) {
int u = p.first;
if (u == pr) {
continue;
}
spec[u] = p.second;
Dfs(u, v);
fs[v] += fs[u];
}
};
Dfs(0, 0);
vector<int> mn(cc, 1e9);
for (auto& p : q) {
int u = p[0];
int v = p[1];
int w = p[2];
if (dep[u] > dep[v]) {
swap(u, v);
}
while (dep[v] > dep[u]) {
mn[v] = min(mn[v], w);
v = par[v];
}
while (v != u) {
mn[v] = min(mn[v], w);
mn[u] = min(mn[u], w);
u = par[u];
v = par[v];
}
}
long long nans = 0;
for (int i = 1; i < cc; i++) {
if (spec[i]) {
nans += fs[i] * mn[i];
}
}
ans = max(ans, nans);
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
