@[Qllllll](/space/show?uid=210311)
我在44
by 决心少年 @ 2019-11-01 13:12:21
@[Qllllll](/space/show?uid=210311)
https://www.luogu.org/record/26082607
过了！！！
谢谢大佬！！！
by 决心少年 @ 2019-11-01 13:13:48
AC代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int fu[20000001],n,m;
int getfa(int x)//得到顶点x的总根
{
if(fu[x]==x)
return x;
else fu[x]=getfa(fu[x]);
return fu[x];
//x=3-->getfa(x=3)->getfa(1)-->getfa(2)==>2
}
struct node //边的信息
{
int start,end,w;
};
node bian[2000001];//不超过5000条边
int comp(node a, node b)//结构 体排序
{
if(a.w<b.w) //如果前面a的权值小于后面的b的权值
return 1;
else return 0;
}
int he(int x,int y)//把xy两个点合并，在一个集合（树）
{//合并是把两个点的总根合并
int a=getfa(x);//得到总根
int b=getfa(y);//把x一条线上的所有点 变成2层
if(a==b)
return 0;//ab总根相同，不能合并，返回0
fu[b]=a;//让前面的点做根
return 1;//合并成功
}
int klsk( )
//最小生成树：让n个点连通的最小代价（铺设道路）
{
int sum=0,num=0,i,j,x,y;
sort(bian+1,bian+1+m,comp);//对m条边进行从小到大排序
//n个点加n-1条边
for(i=1;i<=m;i++)//穷举所有的边
{
x=bian[i].start;//记录每条边的起点和终点
y=bian[i].end;
if(he(x,y)==0)//不能合并，则跳过去
continue;
num++;
sum=sum+bian[i].w;//把这条边加入
if(num==n-1)
break;//加到n-1条结束
}
cout<<sum;
return sum;
}
int main()
{ int i,j,x,y,w;//局部变量
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>x>>y>>w; //图 没有存储链接
bian[i].start=x;
bian[i].end=y;
bian[i].w=w;
}
//最小生成树 只要求最小代价，不需要链接矩阵
//只需要边的权值
//!!初始化并查集
for(i=1;i<=n;i++)
fu[i]=i;
klsk( ) ;
return 0;
}
```
by 决心少年 @ 2019-11-01 13:14:42
@[秦时明月zqy](/space/show?uid=215603) 过了就OK
by Qllllll @ 2019-11-01 13:21:50