题解 P1547 【Out of Hay】

· · 题解

最小生成树算法

根据题目描述，这道题是最小生成树

树：

树是一种植物，木本植物之总名，主要由根、干、枝、叶、花、果组成

一个不存在回路的无向联通图叫做树

生成树：生成树是连通图的极小联通子图。（加边会出现回路，减边变为非连通图）

最小生成树： 生成树的各边权值总和最小的树（最小代价树）

最小生成树一般有两种算法：prim和kruskal。prim一般用于稠密图，kruskal用于稀疏图。

这里介绍一下kruskal。

kruskal算法的基本思想是：始终选择当前可用的最小权值边（贪心

因此很容易想到题目所求的最大边就是最后一条边（每次加边权取max也可以）。

那么怎么判断当前选择的边是否可用呢？

并查集

意思就是说，开始的每个点都是独立的集合，加边的时候就合并起来，如果已经是联通的就跳过。

附上代码```

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int fa[200004];
int n,m,l,r,tot,ans,k;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}//快读 

struct node{
    int fir;//第一个点 
    int sec;//第二个点 
    int data;//边权 
}edge[400005];

inline int find(int x){
    if(x==fa[x])return x;
    else return fa[x]=find(fa[x]);
}

inline bool cmp(node a,node b){
    return a.data<b.data;//结构体排序 
}

inline void kruskal(){
    for(register int i=1;i<=m;i++){
        l=find(edge[i].fir);
        r=find(edge[i].sec);
        if(l==r)continue ;//如果联通就跳过 
        fa[l]=r;//否则就合并 
        k=edge[i].data;//每次更新边权，最后一条边为最大 
    //  maxn=max(maxn,edge[i].data);每次加边取max也可以 
        tot++;
        if(tot==n-1)break;
    }
}

int main(){
    n=read();
    m=read();
    for(register int i=1;i<=n;i++)
    fa[i]=i;//初始化并查集 
    for(register int i=1;i<=m;i++){
        edge[i].fir=read();
        edge[i].sec=read();
        edge[i].data=read();
    }

    sort(edge+1,edge+m+1,cmp);//将边权排序，每次加小的 
    kruskal();
    cout<<k;//我喜欢cout...

    return 0;
}