16pts求调
查看原帖
16pts求调
1015471
liyuwei2333楼主2025/1/15 15:33

#13AC 剩下全WA

#include<bits/stdc++.h>
using namespace std;
int n,m,tot;
int fa[50010];
struct node{
	int u,v,w;
}a[200010];
void add(int u,int v,int w)
{
	a[++tot].u=u;
	a[tot].v=v;
	a[tot].w=w;
}
int cmp(node x,node y)
{
	return x.w<y.w;
}
int find(int x)
{
	if(fa[x]==x) return x;
	return find(fa[x]);
}
int main(){
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	sort(a+1,a+1+m,cmp);
	int cnt=0,sum=0;
	for(int i=1;i<=m;i++)
	{
		int fu=find(a[i].u),fv=find(a[i].v);
		if(fu==fv)
		{
			continue;
		}
		cnt++;
		sum+=a[i].w;
		fa[fu]=fv;
		if(cnt==n-1)
		{
			printf("%d",sum);
			return 0;
		}
	}
	printf("orz");
	return 0;
}

2025/1/15 15:33
加载中...