| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15929 |
2015-08-02T06:13:54 Z |
myungwoo |
Toll (APIO13_toll) |
C++14 |
|
0 ms |
7588 KB |
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXM 300005
#define pb push_back
#define sz(v) ((int)(v).size())
typedef long long lld;
int N, M, K, C;
int A[MAXN];
int par[MAXN], num[MAXN], sz[23], H[23], tpar[23];
int up[23], subtree_sz[23];
vector <int> con[23], tcon[23], tconv[23];
struct EDGE{
int a, b, c;
bool in_mst, is_critical;
} E[MAXM], F[21];
int cp(int n){ return par[n] == n ? n : (par[n] = cp(par[n])); }
void dfs(int n, int from)
{
subtree_sz[n] = sz[n];
for (int i=sz(tcon[n]);i--;){
int t = tcon[n][i], v = tconv[n][i];
if (t == from) continue;
H[t] = H[n] + 1; up[t] = v; tpar[t] = n; dfs(t, n);
subtree_sz[n] += subtree_sz[t];
}
}
int main()
{
scanf("%d%d%d", &N, &M, &K);
for (int i=1;i<=M;i++) scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].c);
for (int i=1;i<=K;i++) scanf("%d%d", &F[i].a, &F[i].b);
for (int i=1;i<=N;i++) scanf("%d", A+i);
sort(E+1, E+M+1, [](const EDGE &a, const EDGE &b){
return a.c < b.c;
});
for (int i=1;i<=N;i++) par[i] = i;
for (int i=1;i<=M;i++){
int a = cp(E[i].a), b = cp(E[i].b);
if (a == b) continue;
par[b] = a;
E[i].in_mst = 1;
}
for (int i=1;i<=N;i++) par[i] = i;
for (int i=1;i<=K;i++){
int a = cp(F[i].a), b = cp(F[i].b);
par[b] = a;
}
for (int i=1;i<=M;i++) if (E[i].in_mst){
int a = cp(E[i].a), b = cp(E[i].b);
if (a == b) E[i].is_critical = 1;
par[b] = a;
}
for (int i=1;i<=N;i++) par[i] = i;
for (int i=1;i<=M;i++) if (E[i].in_mst && !E[i].is_critical){
int a = cp(E[i].a), b = cp(E[i].b);
if (a > b) swap(a, b);
par[b] = a;
}
for (int i=1;i<=N;i++) if (cp(i) == i){
num[i] = ++C;
}
for (int i=1;i<=N;i++) sz[num[cp(i)]] += A[i];
vector <EDGE> critical;
for (int i=1;i<=N;i++) if (E[i].is_critical){
int a = num[cp(E[i].a)] , b = num[cp(E[i].b)];
critical.pb({a, b, E[i].c});
con[a].pb(b); con[b].pb(a);
}
for (int i=1;i<=K;i++) F[i].a = num[cp(F[i].a)], F[i].b = num[cp(F[i].b)];
lld ans = 0;
for (int msk=1;msk<(1<<K);msk++){
for (int i=1;i<=C;i++) par[i] = i, tcon[i].clear();
bool is_cycle = 0;
for (int i=1;i<=K;i++) if (msk & (1 << (i-1))){
int a = cp(F[i].a), b = cp(F[i].b);
if (a == b){ is_cycle = 1; break; }
tcon[F[i].a].pb(F[i].b); tconv[F[i].a].pb(2e9);
tcon[F[i].b].pb(F[i].a); tconv[F[i].b].pb(2e9);
par[b] = a;
}
if (is_cycle) continue;
vector <EDGE> not_in_mst;
for (auto &e: critical){
int a = cp(e.a), b = cp(e.b);
if (a == b) not_in_mst.pb(e);
else{
par[b] = a;
tcon[e.a].pb(e.b); tconv[e.a].pb(e.c);
tcon[e.b].pb(e.a); tconv[e.b].pb(e.c);
}
}
H[1] = 1; dfs(1, 0);
for (auto &e: not_in_mst){
int a = e.a, b = e.b;
if (H[a] < H[b]) swap(a, b);
while (H[a] > H[b]){
up[a] = min(up[a], e.c);
a = tpar[a];
}
while (a != b){
up[a] = min(up[a], e.c); up[b] = min(up[b], e.c);
a = tpar[a]; b = tpar[b];
}
}
lld val = 0;
for (int i=2;i<=C;i++) val += up[i] * subtree_sz[i];
ans = max(ans, val);
}
printf("%lld\n", ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
7588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
