记录如下,下了第三个测试点但是数据有点多看的眼都花了qwq
数据还是不放了吧,太多了谁会手推五十个点的最小生成树啊qwq
代码如下
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll n,m,x,y,z,f[1000000],ans=0,qwq=0;
struct gs
{
ll a,b,c;
}bian[1000000];
bool cmp(gs g,gs s)
{
return g.c<s.c;
}
ll find(ll x)
{
if(f[x]==x) return x;
else find(f[x]);
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) f[i]=i;
for(ll i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
bian[i].a=x;
bian[i].b=y;
bian[i].c=z;
}
sort(bian+1,bian+m+1,cmp);
//cout<<"start"<<endl;
for(ll i=1;i<=m;i++)
{
ll f1=find(bian[i].a),f2=find(bian[i].b);
if(f1!=f2)
{
//cout<<bian[i].a<<' '<<bian[i].b<<" "<<f1<<' '<<f2<<endl;
if(f1==bian[i].a) f1=f2;
f[bian[i].a]=f1;
f[bian[i].b]=f1;
ans+=bian[i].c;
}
}
for(ll i=1;i<=n;i++)//我想的是如果图不连通会有1+个根为自己的点,先纪录下来一个,再有多的就说明不连通了
{
if(f[i]==i&&qwq==1)
{
printf("orz");
return 0;
}
else if(f[i]==i) qwq++;
}
printf("%lld",ans);
return 0;
}
不胜感激!!!!