记录编号	598799	评测结果	AAAAAAAAAA
题目名称	t2	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	2.046 s
提交时间	2025-02-20 20:18:43	内存使用	19.48 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=200010,M=300010;
struct eg
{
	int x,y,z,bi;
}bs[2*M];
int n1,n2,m1,m2;
bool cmp(eg a,eg b){return a.z<b.z;}
int ans;
int fa[3][N],sz[3][N],l1,l2;
int fid(int x,int xb)
{
	if(fa[xb][x]==x) return x;
	return fa[xb][x]=fid(fa[xb][x],xb);
}
void hb(int x,int y,int xb)
{
	if(xb==1) l1--;else l2--;
	x=fid(x,xb);y=fid(y,xb);
	if(sz[xb][x]>sz[xb][y]) swap(x,y);
	fa[xb][x]=y;sz[xb][y]+=sz[xb][x];
	return;
}
signed main()
{
	freopen("emptyfist.in","r",stdin);
	freopen("emptyfist.out","w",stdout);
	scanf("%lld%lld%lld%lld",&n1,&n2,&m1,&m2);
	for(int i=1;i<=n1;i++) fa[1][i]=i,sz[1][i]=1;for(int i=1;i<=n2;i++) fa[2][i]=i,sz[2][i]=1;l1=n1,l2=n2;
	for(int i=1;i<=m1+m2;i++) {
		
	scanf("%lld%lld%lld",&bs[i].x,&bs[i].y,&bs[i].z);
		bs[i].bi=i;
	}
	sort(bs+1,bs+1+m1+m2,cmp);
	for(int i=1;i<=m1+m2;i++)
	{
		if((bs[i].bi<=m1&&fid(bs[i].x,1)==fid(bs[i].y,1))||(bs[i].bi>m1&&fid(bs[i].x,2)==fid(bs[i].y,2))) continue;
		if(bs[i].bi<=m1) ans+=bs[i].z*l2,hb(bs[i].x,bs[i].y,1);
		else ans+=bs[i].z*l1,hb(bs[i].x,bs[i].y,2);
	}
	printf("%lld",ans);
	return 0;
}