kruskal算法
对着书打的
但是测试样例时输出的就是orz,没看出来哪里有问题
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,f[5005],ans;
struct fff
{
int z,x,y;
}d[200005];
int find(int k)//并查集路径压缩
{
if(f[k]==k)return k;
return f[k]=find(f[k]);
}
bool cmp(fff a,fff b)
{
return a.z<b.z;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)cin>>d[i].z>>d[i].x>>d[i].y;
sort(d+1,d+m+1,cmp);
int f1,f2,k=0;
for(int i=1;i<=m;i++)
{
f1=find(d[i].x);
f2=find(d[i].y);
if(f1!=f2)
{
ans+=d[i].z;
f[f1]=f2;//直接让祖先等于另一个祖先
k++;//记录有多少个边加入树
if(k==n-1)break;//如果有n-1个边,则完成了最小生成树
}
}
if(k<n-1)cout<<"orz";
else cout<<ans;
//fclose(stdin);
//fclose(stdout);
return 0;
}