#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)
using namespace std;
typedef long long LL;
typedef pair <int, int> II;
typedef pair <LL, int> LLI;
const int N = 1e5 + 10;
int n, m, q;
int a[N], h[N], b[N], wei[N], par[N];
int p[N][25], f[N][25];
bool fre[N];
LL ans = 0;
LL c[N];
vector <II> pos[N];
vector <int> L;
set <II> adj[N];
map <int, bool> change[N];
struct DSU {
int p[N];
void Init() {
memset(p, -1, sizeof p);
}
int Root(int u) {
return p[u] < 0 ? u : p[u] = Root(p[u]);
}
bool Union(int u, int v) {
u = Root(u); v = Root(v);
if (u == v) return false;
if (p[u] > p[v]) swap(u, v);
p[u] += p[v];
p[v] = u;
return true;
}
} DSU;
struct Edge {
int u, v, w;
Edge () {}
Edge (int u, int v, int w) : u(u), v(v), w(w) {}
bool operator < (const Edge &that) const {
return w < that.w;
}
} E[N];
void DFS(int u) {
for (set <II> :: iterator it = adj[u].begin(); it != adj[u].end(); ++it) {
int v = it -> first, w = it -> second;
if (v == p[u][0]) continue;
a[v] = w; h[v] = h[u] + 1;
p[v][0] = u;
f[v][0] = v;
DFS(v);
}
}
int InitLCA() {
for (int j = 1; 1 << j <= n; ++j)
FOR(i, 1, n) {
p[i][j] = p[p[i][j - 1]][j - 1];
int x = f[i][j - 1], y = f[p[i][j - 1]][j - 1];
if (a[x] < a[y]) f[i][j] = y;
else f[i][j] = x;
}
}
II LCA(int u, int v) {
if (h[u] < h[v]) swap(u, v);
int k = 0;
FOD(i, 20, 0) if (h[u] - (1 << i) >= h[v]) {
if (a[f[u][i]] > a[k]) k = f[u][i];
u = p[u][i];
}
if (u == v) return II(u, k);
FOD(i, 20, 0) if (p[u][i] != p[v][i]) {
if (a[f[u][i]] > a[k]) k = f[u][i];
if (a[f[v][i]] > a[k]) k = f[v][i];
u = p[u][i];
v = p[v][i];
}
if (a[f[u][0]] > a[k]) k = f[u][0];
if (a[f[v][0]] > a[k]) k = f[v][0];
return II(p[u][0], k);
}
void DP(int u) {
c[u] = b[u];
for (set <II> :: iterator it = adj[u].begin(); it != adj[u].end(); ++it) {
int v = it -> first, w = it -> second;
if (v == par[u]) continue;
par[v] = u; wei[v] = w;
if (change[u][v] == true) fre[v] = true;
DP(v);
c[u] += c[v];
}
}
LL Compute() {
FOR(i, 1, n) fre[i] = false;
DP(1);
LL ans = 0;
FOR(i, 1, n) if (fre[i] == true) ans += (LL)wei[i] * c[i];
return ans;
}
void Try(int i) {
if (i >= L.size()) {
ans = max(ans, Compute());
return;
}
Try(i + 1);
int pu = p[L[i]][0], pv = L[i];
adj[pu].erase(II(pv, a[L[i]]));
adj[pv].erase(II(pu, a[L[i]]));
REP(k, 0, pos[L[i]].size()) {
int u = pos[L[i]][k].first, v = pos[L[i]][k].second;
adj[u].insert(II(v, a[L[i]]));
adj[v].insert(II(u, a[L[i]]));
change[u][v] = change[v][u] = true;
Try(i + 1);
change[u][v] = change[v][u] = false;
adj[u].erase(II(v, a[L[i]]));
adj[v].erase(II(u, a[L[i]]));
}
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d%d%d", &n, &m, &q);
FOR(i, 1, m) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
E[i] = Edge(u, v, w);
}
sort(E + 1, E + m + 1);
DSU.Init();
FOR(i, 1, m) {
int u = E[i].u, v = E[i].v, w = E[i].w;
if (DSU.Union(u, v) == true) {
adj[u].insert(II(v, w));
adj[v].insert(II(u, w));
}
}
DFS(1);
InitLCA();
FOR(i, 1, q) {
int x, y; scanf("%d%d", &x, &y);
II res = LCA(x, y);
pos[res.second].push_back(II(x, y));
}
FOR(i, 1, n) scanf("%d", &b[i]);
FOR(i, 1, n) if (pos[i].size()) L.push_back(i);
Try(0);
cout << ans;
return 0;
}
Compilation message
toll.cpp: In function 'int InitLCA()':
toll.cpp:80:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
toll.cpp: In function 'void Try(int)':
toll.cpp:122:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i >= L.size()) {
^
toll.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
toll.cpp:130:5: note: in expansion of macro 'REP'
REP(k, 0, pos[L[i]].size()) {
^
toll.cpp: In function 'int main()':
toll.cpp:147:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &q);
^
toll.cpp:149:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, w; scanf("%d%d%d", &u, &v, &w);
^
toll.cpp:164:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d", &x, &y);
^
toll.cpp:168:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
FOR(i, 1, n) scanf("%d", &b[i]);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
37676 KB |
Output is correct |
| 2 |
Correct |
3 ms |
37676 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
37676 KB |
Output is correct |
| 2 |
Correct |
3 ms |
37676 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
37676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
37676 KB |
Output is correct |
| 2 |
Correct |
3 ms |
37676 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
37676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
37676 KB |
Output is correct |
| 2 |
Correct |
3 ms |
37676 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
37676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
37676 KB |
Output is correct |
| 2 |
Correct |
3 ms |
37676 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
37676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
