最小生成树

最小生成树

基本概念

最小生成树是用最小的代价来使这个图联通。

题目链接

它输入的有连接两条边的代价，我们要在这个图是联通的情况下，付出的代价最小。
前置知识：并查集

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;
}