#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr int inf = 1 << 30;
#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 UF2 {
array<int, 22> data;
UF2() { fill(data.begin(), data.end(), -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 Edge {
int 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);
int L = 1;
REP(i, K) {
if (uft.is_same(A[i].first, A[i].second)) --L;
++L;
uft.unite(A[i].first, A[i].second);
}
vector<vector<int>> graph(N);
for (const auto &[cost, a, b] : E) {
if (uft.is_same(a, b)) continue;
uft.unite(a, b);
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<char> used(N);
vector<vector<int>> groups(L);
int cnt = 0;
REP(i, N) {
if (used[i]) continue;
auto dfs = [&](auto &&self, const int v) -> void {
used[v] = true;
groups[cnt].push_back(v);
for (const int t : graph[v]) {
if (used[t]) continue;
self(self, t);
}
};
dfs(dfs, i);
++cnt;
}
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;
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;
UF2 uft;
vector<vector<pair<int, int>>> tree(N);
vector<int> nec(N);
REP(bit, 1 << K) {
REP(i, N) tree[i].clear();
fill(uft.data.begin(), uft.data.end(), -1);
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
356 KB |
Output is correct |
| 6 |
Correct |
6 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
356 KB |
Output is correct |
| 6 |
Correct |
6 ms |
340 KB |
Output is correct |
| 7 |
Correct |
420 ms |
11480 KB |
Output is correct |
| 8 |
Correct |
406 ms |
11352 KB |
Output is correct |
| 9 |
Correct |
389 ms |
11496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
356 KB |
Output is correct |
| 6 |
Correct |
6 ms |
340 KB |
Output is correct |
| 7 |
Correct |
420 ms |
11480 KB |
Output is correct |
| 8 |
Correct |
406 ms |
11352 KB |
Output is correct |
| 9 |
Correct |
389 ms |
11496 KB |
Output is correct |
| 10 |
Correct |
1546 ms |
11484 KB |
Output is correct |
| 11 |
Execution timed out |
2578 ms |
11484 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
