本人使用Kruskal算法 请尝试观察如下代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
const int maxm=2e5+7;

int fa[maxn];
int sz[maxn];

void set_make(int len)
{
	for(int i=1;i<=len;i++)
	{
		fa[i]=i;
		sz[i]=1;
	}
}

struct edge
{
	int a;
	int b;
	int c;
};

edge edges[maxm];

bool operator <(edge x,edge y)
{
	if(x.c<y.c)return true;
	else return false;
}

int find(int n)
{
	if(fa[n]==n)return fa[n];
	else return fa[n]=find(fa[n]);
}

bool merge(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y)return false;
	else
	{
		if(sz[x]>sz[y])swap(x,y);
		fa[x]=y;
		sz[y]+=sz[x];
		return true;
	}
}

bool check(int len)
{
	int cnt=0;
	for(int i=1;i<=len;i++)
	{
		if(fa[i]==i)
		{
			cnt++;
			if(cnt>1)return false;
		}
	}
	return true;
}

int main()
{
	int n=0,m=0,res=0;
	cin>>n>>m;
	set_make(n);
	for(int i=1;i<=m;i++)
	{
		cin>>edges[i].a>>edges[i].b>>edges[i].c;
	}
	sort(edges,edges+m+1);
	for(int i=1;i<=m;i++)
	{
		if(m==1)cout<<edges[1].c;
		if(check(n)==true)
		{
			cout<<res;
			return 0;
		}
		if(merge(edges[i].a,edges[i].b)==false)
		{
			//cout<<"DON'T"<<endl;
			continue;
		}
		else
		{
			//cout<<"Add edge between "<<edges[i].a<<' '<<" and "<<edges[i].b<<endl;
			res+=edges[i].c;
		}
	}
	cout<<"orz";
	return 0;
}

现在下面给出核心改正部分：

else
		{
			//cout<<"Add edge between "<<edges[i].a<<' '<<" and "<<edges[i].b<<endl;
			res+=edges[i].c;
			n--;
			//cout<<"Now there are "<<n<<" sets"<<endl;
			if(n==1)
			{
				cout<<res;
				return 0;
			}
		}

与此同时，原 bool check() 的检查部分注释掉，废弃不用。 检查 连通块 的位置务必注意，如本代码，当i>m时，将无法进入循环输出结果。 希望能帮助到有需要的人，共勉。