#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e15;
const ll MAXN=1e5+6;
const ll MAXM=3e5+6;
struct edge
{
ll u,v,w;
ll idx;
bool operator<(edge const& other)const
{
return w<other.w;
}
};
ll ans,sum;
ll n,m,k;
bool alwaysin[MAXN];
vector<pair<ll,ll> >g[MAXN];
ll pari[MAXN];
ll pari1[MAXN];
vector<edge>sometimes_in;
edge old[MAXM];
edge nw[20];
vector<ll>comps;
struct DSU
{
ll par[MAXN],sz[MAXN],h[MAXN];
void init()
{
for(ll i=1;i<MAXN;i++)
{
par[i]=i;sz[i]=1;
h[i]=pari[i];
}
}
void init(vector<ll>v)
{
for(auto xd:v)
{
par[xd]=xd;
sz[xd]=1;
}
}
ll getRoot(ll u)
{
if(u==par[u])return u;
return par[u]=getRoot(par[u]);
}
void join(ll p,ll q)
{
if(sz[p]>sz[q])
{
par[q]=p;
sz[p]+=sz[q];
h[p]+=h[q];
}
else
{
par[p]=q;
sz[q]+=sz[p];
h[q]+=h[p];
}
}
}dsu1,dsu2;
ll lei[MAXN];
ll atmost[MAXN];
ll par[MAXN];
ll depth[MAXN];
ll subtree[MAXN];
void dfs1(ll u,ll p,ll last_edge_idx=-69)
{
atmost[u]=INF;
depth[u]=depth[p]+1;
subtree[u]=pari1[u];
lei[u]=last_edge_idx;
par[u]=p;
for(auto xd:g[u])
{
if(xd.first==p)continue;
dfs1(xd.first,u,xd.second);
subtree[u]+=subtree[xd.first];
}
}
void takovai(edge e)
{
ll x=e.u,y=e.v;
if(depth[x]<depth[y])swap(x,y);
while(depth[x]>depth[y])
{
atmost[x]=min(atmost[x],e.w);
x=par[x];
}
while(x!=y)
{
atmost[x]=min(atmost[x],e.w);
atmost[y]=min(atmost[y],e.w);
x=par[x];y=par[y];
}
}
void dfs(ll u,ll p)
{
for(auto xd:g[u])
{
if(xd.first==p)continue;
if(xd.second>m)
{
//cout<<"%%%\n";
sum+=atmost[xd.first]*subtree[xd.first];
}
dfs(xd.first,u);
}
}
int main()
{
cin>>n>>m>>k;
for(ll i=1;i<=m;i++)
{
cin>>old[i].u>>old[i].v>>old[i].w;
old[i].idx=i;
}
sort(old+1,old+m+1);
for(ll i=0;i<k;i++)
{
cin>>nw[i].u;
cin>>nw[i].v;
nw[i].idx=m+i+1;
}
for(ll i=1;i<=n;i++)cin>>pari[i];
dsu1.init();
for(ll i=0;i<k;i++)
{
ll p=dsu1.getRoot(nw[i].u);
ll q=dsu1.getRoot(nw[i].v);
if(p!=q)dsu1.join(p,q);
}
for(ll i=1;i<=m;i++)
{
ll p=dsu1.getRoot(old[i].u);
ll q=dsu1.getRoot(old[i].v);
if(p!=q)
{
alwaysin[i]=1;
dsu1.join(p,q);
}
}
dsu1.init();
for(ll i=1;i<=m;i++)
{
ll p=dsu1.getRoot(old[i].u);
ll q=dsu1.getRoot(old[i].v);
if(p!=q)
{
if(alwaysin[i]!=1)sometimes_in.push_back(old[i]);
dsu1.join(p,q);
}
}
dsu1.init();
for(ll i=1;i<=m;i++)
{
if(alwaysin[i])
{
dsu1.join(dsu1.getRoot(old[i].u),dsu1.getRoot(old[i].v));
}
}
for(ll i=1;i<=n;i++)
{
if(dsu1.getRoot(i)==i)comps.push_back(i);
}
for(ll i=0;i<k;i++)
{
nw[i].u=dsu1.getRoot(nw[i].u);
nw[i].v=dsu1.getRoot(nw[i].v);
}
for(ll i=0;i<sometimes_in.size();i++)
{
sometimes_in[i].u=dsu1.getRoot(sometimes_in[i].u);
sometimes_in[i].v=dsu1.getRoot(sometimes_in[i].v);
}
/*for(ll i=1;i<=m;i++)
{
if(alwaysin[i])
{
cout<<old[i].u<<" "<<old[i].v<<" "<<old[i].w<<endl;
}
}*/
ll root=dsu1.getRoot(1);
for(ll i=0;i<comps.size();i++)
{
pari1[comps[i]]=dsu1.h[comps[i]];
}
for(ll mask=1;mask<(1<<k);mask++)
{
for(ll i=0;i<comps.size();i++)
{
dsu2.par[comps[i]]=comps[i];
dsu2.sz[comps[i]]=1;
dsu2.h[comps[i]]=dsu1.h[comps[i]];
}
bool ne_stava_brat=0;
for(ll i=0;i<comps.size();i++)g[comps[i]].clear();
for(ll i=0;i<k;i++)
{
if(mask&(1<<i))
{
ll p=dsu1.getRoot(nw[i].u);
ll q=dsu1.getRoot(nw[i].v);
if(p==q)
{
ne_stava_brat=1;
break;
}
dsu1.join(p,q);
g[nw[i].u].push_back({nw[i].v,nw[i].idx});
g[nw[i].v].push_back({nw[i].u,nw[i].idx});
}
}
if(ne_stava_brat)continue;
vector<edge>ivan;
for(ll i=0;i<sometimes_in.size();i++)
{
ll p=dsu1.getRoot(sometimes_in[i].u);
ll q=dsu1.getRoot(sometimes_in[i].v);
if(p==q){ivan.push_back(sometimes_in[i]);continue;}
dsu1.join(p,q);
g[sometimes_in[i].u].push_back({sometimes_in[i].v,i});
g[sometimes_in[i].v].push_back({sometimes_in[i].u,i});
//ivan.push_back(sometimes_in[i]);
}
dfs1(root,0);
for(auto xd:ivan)takovai(xd);
sum=0;
dfs(root,0);
ans=max(ans,sum);
}
cout<<ans<<endl;
return 0;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:175:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(ll i=0;i<sometimes_in.size();i++)
| ~^~~~~~~~~~~~~~~~~~~~
toll.cpp:188:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | for(ll i=0;i<comps.size();i++)
| ~^~~~~~~~~~~~~
toll.cpp:194:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for(ll i=0;i<comps.size();i++)
| ~^~~~~~~~~~~~~
toll.cpp:201:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for(ll i=0;i<comps.size();i++)g[comps[i]].clear();
| ~^~~~~~~~~~~~~
toll.cpp:220:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
220 | for(ll i=0;i<sometimes_in.size();i++)
| ~^~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5248 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5248 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5248 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5248 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
