#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair
typedef long long ll;
const int maxn = 2e5+10;
const int mod = 1e9+7;
const ll inf = 1e18+10;
int n, m, k;
struct dsu
{
int par[maxn];
dsu() {memset(par, -1, sizeof par);}
void reset() {fill(par, par+k+3, -1);}
int get_par(int v)
{
if(par[v] < 0) return v;
return par[v] = get_par(par[v]);
}
void add(int u, int v)
{
u = get_par(u);
v = get_par(v);
if(u == v) return;
if(par[u] < par[v]) swap(u,v);
par[v] += par[u];
par[u] = v;
}
bool ask(int u, int v) {return (get_par(u) == get_par(v));}
} dsu;
vector<pii> T[maxn];
int par[maxn][20], dp[maxn], st[maxn], sz[maxn], comp[maxn], p[maxn], mark[maxn], h[maxn], sum[maxn], Root, siz, num;
void dfs(int v)
{
dp[Root] += sum[v] * p[v];
comp[v] = num; siz += p[v]; sz[num] += p[v];
mark[v] = 1;
st[v] = p[v];
for(int i = 1; (1<<i) <= h[v]; i++)
par[v][i] = par[par[v][i-1]][i-1];
for(auto e : T[v])
{
int u = e.F, w = e.S;
if(!mark[u])
{
h[u] = h[v] + 1;
sum[u] = sum[v] + w;
par[u][0] = v;
dfs(u);
st[v] += st[u];
}
}
}
void dfs_up(int v, int c)
{
if(v != Root) dp[v] = dp[par[v][0]] + c * (siz - 2 * st[v]);
for(auto e : T[v])
{
int u = e.F, w = e.S;
if(u != par[v][0])
dfs_up(u,w);
}
}
int get_par(int v, int he)
{
int i = 0;
while(he)
{
if(he&1) v = par[v][i];
he >>= 1;
i++;
}
return v;
}
int lca(int u, int v)
{
if(h[u] > h[v]) swap(u,v);
v = get_par(v,h[v]-h[u]);
if(u == v) return v;
for(int i = 19; i >= 0; i--)
if(par[v][i] != par[u][i])
{
v = par[v][i];
u = par[u][i];
}
return par[v][0];
}
int dis(int u, int v)
{
return sum[v] + sum[u] - 2 * sum[lca(u,v)];
}
vector<pair<int,pii>> Tree[22];
int pa[maxn], W[maxn], Sm[maxn], yal[maxn], stt[maxn];
void dfs_T(int v)
{
yal[1] = 1;
W[v] = inf;
stt[v] = sz[v];
for(auto e : Tree[v])
{
int u = e.F, v1 = e.S.F, u1 = e.S.S;
if(u != pa[v])
{
pa[u] = v;
dfs_T(u);
stt[v] += stt[u];
}
}
}
ll ans = 0;
void reset()
{
ans = 0;
dsu.reset();
for(int i = 1; i <= k; i++)
{
Tree[i].clear();
W[i] = inf;
pa[i] = 0;
Sm[i] = 0;
yal[i] = 0;
stt[i] = 0;
}
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>> n >> m >> k;
vector<pair<int,pii>> edge, Bedge; vector<pii> Redge;
for(int i = 1, u, v, c; i <= m; i++)
{
cin>> u >> v >> c;
edge.push_back({c,{u,v}});
}
sort(edge.begin(), edge.end());
for(int i = 1, u, v; i <= k; i++)
{
cin>> u >> v;
Redge.push_back({u,v});
dsu.add(u,v);
}
for(auto e : edge)
{
int u = e.S.F, v = e.S.S, w = e.F;
if(!dsu.ask(u,v))
{
T[u].push_back({v,w});
T[v].push_back({u,w});
dsu.add(u,v);
}
else Bedge.push_back(e);
}
for(int i = 1; i <= n; i++) cin>> p[i];
// comp[Root = 1] = 1
for(int i = 1; i <= n; i++)
if(!mark[i])
{
num++; siz = 0;
Root = i;
dfs(i);
dfs_up(i,0);
}
ll last_ans = 0;
for(int msk = 0; msk < (1<<k); msk++)
{
// in k ta dori nabashano ham bayad check koni
reset();
for(int i = 0; i < k; i++)
if((1<<i) & msk)
{
int u = comp[Redge[i].F], v = comp[Redge[i].S];
int u1 = Redge[i].F, v1 = Redge[i].S;
dsu.add(u,v);
Tree[u].push_back({v,{u1,v1}});
Tree[v].push_back({u,{v1,u1}});
}
for(auto e : Bedge)
{
int w = e.F, u = comp[e.S.F], v = comp[e.S.S];
int u1 = e.S.F, v1 = e.S.S;
if(!dsu.ask(u,v))
{
dsu.add(u,v);
Tree[u].push_back({v,{u1,v1}});
Tree[v].push_back({u,{v1,u1}});
}
}
dfs_T(1);
for(auto e : Bedge)
{
int w = e.F, u = comp[e.S.F], v = comp[e.S.S];
bool seen[k+2];
memset(seen, 0, sizeof seen);
while(u != 1)
{
(seen[u] ^= 1);
u = pa[u];
}
while(v != 1)
{
(seen[v] ^= 1);
v = pa[v];
}
for(int i = 1; i <= k+1; i++)
if(seen[i]) W[i] = min(W[i],w);
if(u == pa[v]) W[v] = 0;
if(v == pa[u]) W[u] = 0;
}
for(int i = 2; i <= k+1; i++) ans += stt[i] * W[i];
last_ans = max(last_ans, ans);
}
cout<< last_ans;
}
Compilation message
toll.cpp: In function 'void dfs_T(long long int)':
toll.cpp:124:16: warning: unused variable 'v1' [-Wunused-variable]
int u = e.F, v1 = e.S.F, u1 = e.S.S;
^~
toll.cpp:124:28: warning: unused variable 'u1' [-Wunused-variable]
int u = e.F, v1 = e.S.F, u1 = e.S.S;
^~
toll.cpp: In function 'int main()':
toll.cpp:212:8: warning: unused variable 'w' [-Wunused-variable]
int w = e.F, u = comp[e.S.F], v = comp[e.S.S];
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
6784 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6656 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
6784 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6656 KB |
Output is correct |
| 3 |
Runtime error |
128 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
6784 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6656 KB |
Output is correct |
| 3 |
Runtime error |
128 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
6784 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6656 KB |
Output is correct |
| 3 |
Runtime error |
128 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
6784 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6656 KB |
Output is correct |
| 3 |
Runtime error |
128 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
