#include<bits/stdc++.h>
using namespace std;
const int M=3e5+2;
const int N=1e5+2;
const int K=41;
const int inf=1e9+7;
vector<pair<int,pair<int,int> > > edge,tree,res,lis;
vector<pair<int,int> > damn,adj[N];
int head[N],grp[N],sum[K],a[N],max1[K],hihixd[K],level[K];
pair<int,int> par[K];
int findd(int x){
if(head[x]<0){
return x;
}
int y=findd(head[x]);
head[x]=y;
return y;
}
void unionn(int x,int y){
x=findd(x),y=findd(y);
head[x]+=head[y];
head[y]=x;
}
bool samee(int x,int y){
return findd(x)==findd(y);
}
void dfs(int x,int p){
//cout<<x<<endl;
grp[x]=grp[p];
sum[grp[x]]+=a[x];
for(int i=0;i<adj[x].size();i++){
if(adj[x][i].first!=p){
dfs(adj[x][i].first,x);
}
}
}
void dfs1(int x,int p){
hihixd[x]=sum[x];
for(int i=0;i<adj[x].size();i++){
if(adj[x][i].first!=p){
level[adj[x][i].first]=level[x]+1;
dfs1(adj[x][i].first,x);
hihixd[x]+=hihixd[adj[x][i].first];
par[adj[x][i].first]={x,adj[x][i].second};
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,i,j,k,l,m,num,com=0,z;
long long ans=0,hihi;
cin>>n>>m>>num;
for(i=1;i<=m;i++){
cin>>j>>k>>l;
edge.push_back({l,{j,k}});
}
for(i=1;i<=num;i++){
cin>>j>>k;
damn.push_back({j,k});
}
for(i=1;i<=n;i++){
head[i]=-1;
}
sort(edge.begin(),edge.end());
for(i=0;i<m;i++){
j=edge[i].second.first;
k=edge[i].second.second;
//cout<<i<<' '<<edge[i].first<<' '<<j<<' '<<k<<endl;
if(!samee(j,k)){
// cout<<j<<' '<<k<<endl;
unionn(j,k);
tree.push_back(edge[i]);
}
}
// cout<<"cac"<<endl;
for(i=1;i<=n;i++){
head[i]=-1;
}
for(i=1;i<=num;i++){
j=damn[i-1].first;
k=damn[i-1].second;
if(!samee(j,k)){
// cout<<j<<' '<<k<<endl;
unionn(j,k);
}
}
for(i=1;i<=n;i++){
cin>>a[i];
}
// com=0;
for(i=0;i<tree.size();i++){
j=tree[i].second.first;
k=tree[i].second.second;
if(!samee(j,k)){
// cout<<j<<' '<<k<<" cac"<<endl;
// com++;
unionn(j,k);
adj[j].push_back({k,tree[i].first});
adj[k].push_back({j,tree[i].first});
}
else{
lis.push_back(tree[i]);
}
}
// assert(com<=n-1-num);
for(i=1;i<=n;i++){
if(!grp[i]){
com++;
grp[i]=com;
dfs(i,i);
// cout<<com<<' '<<i<<endl;
}
}
//pre-computed is ok
// cout<<(1<<num)<<endl;
for(i=0;i<(1<<num);i++){
// cout<<i<<endl;
for(j=1;j<=com;j++){
head[j]=-1;
adj[j].clear();
max1[j]=inf;
}
res.clear();
bool cac=false;
for(j=0;j<num;j++){
k=grp[damn[j].first];
l=grp[damn[j].second];
if(((1<<j)&i)){
if(samee(k,l)){
cac=true;
break;
}
unionn(k,l);
adj[k].push_back({l,j+1});
adj[l].push_back({k,j+1});
cout<<k<<' '<<l<<' '<<j+1<<endl;
}
}
if(cac){
// cout<<j<<' '<<k<<' '<<l<<endl;
continue;
}
// cout<<"lon"<<endl;
for(j=0;j<lis.size();j++){
k=grp[lis[j].second.first];
l=grp[lis[j].second.second];
if(!samee(k,l)){
unionn(k,l);
adj[k].push_back({l,0});
adj[l].push_back({k,0});
}
else{
res.push_back(lis[j]);
}
}
dfs1(grp[1],grp[1]);
// cout<<"lon?"<<endl;
for(j=1;j<=com;j++){
head[j]=-1;
}
for(j=0;j<res.size();j++){
z=res[j].first;
k=grp[res[j].second.first];
l=grp[res[j].second.second];
k=findd(k);
l=findd(l);
// cout<<k<<' '<<l<<' '<<res[j].second.first<<' '<<res[j].second.second<<endl;
while(k!=l){
if(level[k]<level[l]){
swap(k,l);
}
max1[par[k].second]=min(max1[par[k].second],z);
cout<<par[k].second<<endl;
unionn(par[k].first,k);
k=findd(k);
}
}
//cout<<"concactrecon"<<endl;
hihi=0;
for(j=0;j<num;j++){
if(((1<<j)&i)){
k=grp[damn[j].first];
l=grp[damn[j].second];
if(level[k]<level[l]){
swap(k,l);
}
hihi+=hihixd[k]*max1[j+1];
// cout<<hihi
}
}
ans=max(ans,hihi);
// cout<<hihi<<' '<<i<<endl;
}
cout<<ans;
}
/*
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 'void dfs(int, int)':
toll.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
toll.cpp: In function 'void dfs1(int, int)':
toll.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:92:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<tree.size();i++){
~^~~~~~~~~~~~
toll.cpp:145:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<lis.size();j++){
~^~~~~~~~~~~
toll.cpp:162:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<res.size();j++){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
