蒟蒻样例全a WA求条
查看原帖
蒟蒻样例全a WA求条
1373205
dg114514楼主2024/12/9 16:01
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std; 
int fa[234567],n,m,k,a[234567][2],x,y;
struct node{
	int u,v,w;
}e[234567];
int find(int x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[x]=y,a[y][0]+=a[x][0],a[y][1]+=a[x][1];}
int main(){
	cin>>n>>m>>k;
	iota(fa+1,fa+n+1,1);
	for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+n+1,[&](node a,node b){return a.w<b.w;});
	for(int i=1;i<=(k<<1);i++)
		cin>>x,a[x][(i>k)?1:0]++;
	ll ans=0;
	for(int i=1;i<=m;i++){
		int r1=find(e[i].u),r2=find(e[i].v);
		if(r1^r2){
			x=min(a[r2][0],a[r1][1]),y=min(a[r2][1],a[r1][0]);
			ans+=1ll*(x+y)*e[i].w;
			a[r1][0]-=x+y,a[r2][1]-=x+y;
			merge(r1,r2);
		}
	}
	cout<<ans;
}
2024/12/9 16:01
加载中...