最小生成树模板求调
  • 板块灌水区
  • 楼主唯有谔谔
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/1/16 18:29
  • 上次更新2023/10/24 03:57:53
查看原帖
最小生成树模板求调
158821
唯有谔谔楼主2023/1/16 18:29

rt,Kruskal算法,wa了

#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v,w;
}a[100001]; 
int n,m,sum,r=1,l;
bool cmp(edge x,edge y)
{
	return x.w<y.w;
}
int fa[5001];
int find(int x1)
{
	if(fa[x1]==x1) return x1;
	else return fa[x1]=find(fa[x1]);
}
bool ch(int x,int y)
{
	if(find(x)!=find(y)) 
	{
		fa[y]=x;
		return 1;
	}
	else return 0;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].u>>a[i].v>>a[i].w;
	}
	sort(a+1,a+1+m,cmp);
	while(sum!=n-1)
	{
		if(ch(a[r].v,a[r].u)==1)
		{
			sum++;
			l+=a[r].w;
		}
		r++;
		if(r>m&&sum<n-1)
		{
			cout<<"orz";
			return 0;
		}
	}
	cout<<l;
	return 0;
 } 

code

2023/1/16 18:29
加载中...