AcWing 3210. 第3次csp认证 题目4 最优灌溉
原题链接
简单
作者:
Misty.
,
2023-12-03 20:01:40
,
所有人可见
,
阅读 48
克鲁斯卡尔算法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010,M=100010;
int p[N];
int n,m;
struct edge{
int a,b,c;
}e[M];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
bool cmp(edge a,edge b)
{
return a.c<b.c;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i; //初始化并查集
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
e[i]={a,b,c};
}
sort(e+1,e+m+1,cmp);
//for(int i=1;i<=m;i++) cout<<e[i].a<<' '<<e[i].b<<' '<<e[i].c<<' '<<endl;
int res=0;
for(int i=1;i<=m;i++)
{
int a=e[i].a,b=e[i].b,c=e[i].c;
if(find(a)!=find(b))
{
// cout<<"add "<<e[i].c<<endl;
p[find(b)]=find(a);
res+=c;
}
}
cout<<res;
return 0;
}