怎么特判无解?
查看原帖
怎么特判无解?
382274
暗影之梦楼主2021/10/22 20:22

Kruskal,WA了最后一个点

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,m,ans,cnt;
int fa[50001];
struct edge
{
	int u,v,w;
}e[200001];
bool cmp(edge a,edge b)
{
	return a.w<b.w;
}
int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		if(find(e[i].u)!=find(e[i].v))
		{
			ans+=e[i].w;
			fa[find(e[i].u)]=find(e[i].v);
//			if(++cnt==n-1) continue;
		}
	}
	if(cnt==m) cout<<"orz"<<endl;
	else cout<<ans<<endl;
	return 0;
}
2021/10/22 20:22
加载中...