Submission #60538387

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define N 500005
int head[N],ne[N<<1],to[N<<1],num=0;
int fa[N];
int val[N],cnt;
int n1[N],n2[N];
ll ans=0;
int find(int x){
  return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void add(int u,int v){
  num++;
  ne[num]=head[u];
  to[num]=v;
  head[u]=num;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define N 500005

int head[N],ne[N<<1],to[N<<1],num=0;

int fa[N];
int val[N],cnt;
int n1[N],n2[N];
ll ans=0;
int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void add(int u,int v){
	num++;
	ne[num]=head[u];
	to[num]=v;
	head[u]=num;
}

void dfs(int x,int p){
	// cout<<x<<" "<<p<<"\n";
	for(int i=head[x];i>0;i=ne[i]){
		int t=to[i];
		if(t==p)continue;
		dfs(t,x);
		n1[x]+=n1[t];
		n2[x]+=n2[t];
	}
	int pp=min(n1[x],n2[x]);
	// cout<<x<<" "<<val[x]<<" "<<n1[x]<<" "<<n2[x]<<"\n";
	ans+=1ll*pp*val[x];
	n1[x]-=pp;n2[x]-=pp;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int n,m,k;
	cin>>n>>m>>k;
	cnt=n;
	for(int i=1;i<=2*n;i++){
		fa[i]=i;
	}
	vector<array<int,3>> line(m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		line[i-1]={w,u,v};
	}
	sort(line.begin(),line.end());
	for(int i=0;i<m;i++){
		// cout<<line[i][0]<<" "<<line[i][1]<<" "<<line[i][2]<<"\n";
		int fu=find(line[i][1]),fv=find(line[i][2]);
		// cout<<fu<<" "<<fv<<"\n";
		if(fu==fv)continue;
		cnt++;
		fa[fu]=cnt,fa[fv]=cnt;
		val[cnt]=line[i][0];
		add(cnt,fu);
		add(fu,cnt);
		add(cnt,fv);
		add(fv,cnt);
	}
	int rt=find(1);
	// for(int i=1;i<=2*n-1;i++){
	// 	cout<<fa[i]<<" \n"[i==n*2-1];
	// }
	for(int i=1;i<=k;i++){
		int x;
		cin>>x;
		n1[x]++;
	}
	for(int i=1;i<=k;i++){
		int x;
		cin>>x;
		n2[x]++;
	}
	
	dfs(rt,0);

	cout<<ans;

	return 0;
}

Submission Info

Judge Result