Kruskal16pts求助
查看原帖
Kruskal16pts求助
539133
q1uple楼主2022/9/10 12:01
#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v,w;
}e[20005];
int fa[20005];
int n,m,tot=0,ans=0;
int cmp(edge x,edge y)
{
	return x.w<y.w;
}

int find(int x)
{
	if(x!=fa[x])
		return fa[x]=find(fa[x]);
	return x;
}

void kruskal()
{
	sort(e+1,e+n+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int u=find(e[i].u);
		int v=find(e[i].v);
		if(u==v)
			continue;
		ans+=e[i].w;
		fa[u]=v;
		tot++;
		if(n==tot+1)
			break;
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	kruskal();
	if(n==tot+1)
		cout<<ans;
	else
		cout<<"orz"<<endl;
	return 0;
}
2022/9/10 12:01
加载中...