#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll P[maxn];
vector<pli>g[maxn];
ll ww[maxn];
ll nxt[maxn],h[maxn],sz[maxn];
void dfs(ll u,ll p)
{
P[u]=p;
for(auto vv:g[u])
{
int v=vv.fi;
int w=ww[vv.se];
nxt[v]=vv.se;
if(v!=p)
{
h[v]=h[u]+1;
dfs(v,u);
}
}
}
ll ss=0;
ll val[maxn];
void DFS(ll u,ll p)
{
sz[u]=val[u];
for(auto vv:g[u])
{
int v=vv.fi;
int w=ww[vv.se];
if(v!=p)
{
DFS(v,u);
sz[u]+=sz[v];
ss+=sz[v]*w;
}
}
}
void update(ll u,ll v,ll w)
{
while(u!=v)
{
if(h[u]>h[v])
{
ww[nxt[u]]=min(ww[nxt[u]],w);
u=P[u];
}
else
{
ww[nxt[v]]=min(ww[nxt[v]],w);
v=P[v];
}
}
}
ll node=0;
ll lab[maxn];
ll findset(ll x)
{
return lab[x]<0?x:lab[x]=findset(lab[x]);
}
ll sum[maxn];
bool unite(ll u,ll v)
{
u=findset(u);
v=findset(v);
if(u==v) return false;
if(lab[u]>lab[v]) swap(u,v);
lab[u]+=lab[v];
lab[v]=u;
sum[u]+=sum[v];
return true;
}
ll k;
struct edge
{
ll u,v,w;
bool operator<(const edge&o)
{
return w<o.w;
}
}e[maxn],d[maxn];
vector<edge>t2,t3;
ll id[maxn],ans=0;
void cal(ll mask)
{
for(int i=1;i<=node;i++) lab[i]=-1,g[i].clear();
ww[0]=0;
for(int i=1;i<=k;i++) ww[i]=inf;
for(int i=1;i<=k;i++)
{
if(mask>>(i-1)&1)
{
if(unite(d[i].u,d[i].v))
{
g[d[i].u].pb({d[i].v,i});
g[d[i].v].pb({d[i].u,i});
}
}
}
vector<edge>djt;
for(auto zz:t3)
{
if(unite(zz.u,zz.v))
{
g[zz.u].pb({zz.v,0});
g[zz.v].pb({zz.u,0});
}
else
{
djt.pb(zz);
}
}
dfs(id[1],0);
for(auto zz:djt)
{
update(zz.u,zz.v,zz.w);
}
ss=0;
DFS(id[1],0);
ans=max(ans,ss);
}
ll n,m,p[maxn],vv[maxn];
bool in[maxn];
void solve()
{
cin >> n >> m >> k;
for(int i=1;i<=m;i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
}
for(int i=1;i<=k;i++)
{
cin >> d[i].u >> d[i].v ;
d[i].w=inf;
}
for(int i=1;i<=n;i++) cin >> p[i];
sort(e+1,e+m+1);
for(int i=1;i<=n;i++) lab[i]=-1,sum[i]=p[i];
for(int i=1;i<=m;i++)
{
if(unite(e[i].u,e[i].v)) in[i]=true;
}
for(int i=1;i<=n;i++) lab[i]=-1,sum[i]=p[i];
for(int i=1;i<=k;i++)
{
unite(d[i].u,d[i].v);
}
for(int i=1;i<=m;i++)
{
if(unite(e[i].u,e[i].v)) t2.pb(e[i]);
else if(in[i]==true) t3.pb(e[i]);
}
for(int i=1;i<=n;i++) lab[i]=-1,sum[i]=p[i];
for(auto zz:t2)
{
unite(zz.u,zz.v);
}
node=0;
for(int i=1;i<=n;i++)
{
if(findset(i)==i)
{
vv[i]=++node;
val[node]=sum[i];
}
}
for(int i=1;i<=n;i++)
{
id[i]=vv[findset(i)];
}
for(int i=1;i<=k;i++)
{
d[i].u=id[d[i].u];
d[i].v=id[d[i].v];
}
for(auto &zz:t3)
{
zz.u=id[zz.u];
zz.v=id[zz.v];
}
for(int mask=0;mask<(1<<k);mask++)
{
cal(mask);
}
cout << ans;
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
toll.cpp: In function 'void dfs(ll, ll)':
toll.cpp:23:13: warning: unused variable 'w' [-Wunused-variable]
23 | int w=ww[vv.se];
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
4 ms |
31232 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
4 ms |
31232 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
31068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
4 ms |
31232 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
31068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
4 ms |
31232 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
31068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
4 ms |
31232 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
31068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
