最小生成树
基本概念
最小生成树是用最小的代价来使这个图联通。
它输入的有连接两条边的代价,我们要在这个图是联通的情况下,付出的代价最小。
前置知识:并查集
Kruskal
基本概念
- 我们可以先把这写边按照代价排序。接着,我们依次从1到\(n\)枚举这个排好序数组中的元素,依次判断每条边是否已经相通,如果是,那就跳过,否则就连通两条边,并且将计数器加上连接这条边的代价。
- 题目还说,如果怎么都无法让这个图任意两点都联通,就输出\(orz\),那么就可以再用一个计数器,每次连接一条边就加以,表示这个图的边多了一条。最后如果这个计数器不等于\(n-1\),那就说明——这个图不联通!
代码
先定义一个结构体,里面存着\(x,y,z\)。
struct node{
int x,y,z;
};
接下来,输入这个结构体。
vector<node> r(n);
for(int i=0; i<n; i++){
cin>>r[i].x>>r[i].y>>r[i].z;
}
我们可以写一个并查集来判断两条变是否是联通的。
int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
我们知道,要让这个代价最小,我们可以先按照代价\(z\)的大小将\(r\)数组先进行排序。排完序后再判断每两条边是否已经联通,如果没有联通,那么就可以把两条边连接起来。
\(cmp\)排序函数
bool cmp(node x,node y){
return x.z<y.z;
}
stable_sort(r.begin(),r.end(),cmp);
int sum=0,cnt=0;
for(int i=0; i<m; i++){
if(find(r[i].x)!=find(r[i].y)){
fa[find(r[i].x)]=find(r[i].y);
sum=sum+r[i].z;
cnt++;
}
}
最后,我们知道,一个联通图的边是\(n-1\),如果不是,就输出\(orz\)。
if(cnt!=n-1){
cout<<"orz"<<endl;
}
else{
cout<<sum<<endl;
}
完整代码:
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int fa[10010];
struct node{
int x,y,z;
};
bool cmp(node x,node y){
return x.z<y.z;
}
int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++){
fa[i]=i;
}
vector<node> r(m);
for(int i=0; i<m; i++){
cin>>r[i].x>>r[i].y>>r[i].z;
}
stable_sort(r.begin(),r.end(),cmp);
int sum=0,cnt=0;
for(int i=0; i<m; i++){
if(find(r[i].x)!=find(r[i].y)){
fa[find(r[i].x)]=find(r[i].y);
sum=sum+r[i].z;
cnt++;
}
}
if(cnt!=n-1){
cout<<"orz"<<endl;
}
else{
cout<<sum<<endl;
}
return 0;
}
标签:node,联通,int,最小,生成,代价,cmp
From: https://www.cnblogs.com/wrl2010/p/17621835.html