记录编号	598791	评测结果	AAAAAAAAAA
题目名称	t2	最终得分	100
用户昵称	徐诗畅	是否通过	通过
代码语言	C++	运行时间	2.133 s
提交时间	2025-02-20 20:14:52	内存使用	14.58 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n1,m1,n2,m2,fa1[N],fa2[N],siz1,siz2;
int num1=1,num2=1;
struct edge{
	int x,y,w;
}e1[3*N],e2[3*N];
bool cmp(edge a,edge b){return a.w<b.w;}
int find1(int x){return fa1[x]==x?x:fa1[x]=find1(fa1[x]);}
int find2(int x){return fa2[x]==x?x:fa2[x]=find2(fa2[x]);}
void merge1(int x,int y){
	int fx=find1(x),fy=find1(y);
	fa1[fx]=fy;
	if(fx!=fy) siz1--;
}
void merge2(int x,int y){
	int fx=find2(x),fy=find2(y);
	fa2[fx]=fy;
	if(fx!=fy) siz2--;
}
int ans;
signed main(){
	freopen("emptyfist.in","r",stdin);
	freopen("emptyfist.out","w",stdout);
	scanf("%lld%lld%lld%lld",&n1,&n2,&m1,&m2);
	for(int i = 0;i<=n1;i++) fa1[i]=i;
	for(int i = 0;i<=n2;i++) fa2[i]=i;
	siz1=n1; siz2=n2;
	for(int i = 1;i<=m1;i++) scanf("%lld%lld%lld",&e1[i].x,&e1[i].y,&e1[i].w);
	for(int i = 1;i<=m2;i++) scanf("%lld%lld%lld",&e2[i].x,&e2[i].y,&e2[i].w);
	sort(e1+1,e1+1+m1,cmp);
	sort(e2+1,e2+1+m2,cmp);
	for(int i=1;i<=m1+m2;i++){
		if(num1<=m1&&find1(e1[num1].x)==find1(e1[num1].y)){num1++;continue;}
		if(num2<=m2&&find2(e2[num2].x)==find2(e2[num2].y)){num2++;continue;}
		if(num1<=m1&&(num2>m2||e2[num2].w>e1[num1].w)){
			merge1(e1[num1].x,e1[num1].y);
			ans+=siz2*e1[num1].w; num1++;
		}
		else{
			merge2(e2[num2].x,e2[num2].y);
			ans+=siz1*e2[num2].w; num2++;
		}
	}
	printf("%lld",ans);
	return 0;
}