【Acwing】最小生成树繁忙的都市

冷不防 2024-03-31 10:42 60阅读 0赞

[1142. 繁忙的都市 - AcWing题库][1142. _ - AcWing]

题意：

![6713fc4c4e764ab4a0cf4d5daabd9296.png][]

思路：

一般思路：

“分值最大值尽可能小”——二分

我们去二分分值的最大值，对于我们二分出来的分值最大值，我们把小于这个值的边全部连上，看这个图是否连通。这样做显然是合理的，因为分值最大值具有单调性，当分值最大值充分大时，整个图一定是连通的，当分值最大值无穷小时，就没有边可以连了

因此时间复杂度为O(mlogn)

还有一个思路：

利用kruskal的特性

**kruskal的特性：在求最小生成树的过程中，连通块个数是单调递减的，边权数单调递减的，因此根据连通块个数或边权的二分可以直接用kruskal做，这就相当于枚举了**

**kruskal可以构造一棵完美最小生成树，即在构造的过程中生成的树的边权一定是所有边中最小的**

因此这道题可以用kruskal直接做

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=3e2+10,mxe=8e3+10;
    struct ty{
        int u,v,w;
    }edge[mxe<<1];
    bool cmp(ty x,ty y){
        return x.w<y.w;
    }
    int n,m,x,y,w;
    int f[mxn];
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    int kruskal(){
        int ans=0;
        sort(edge+1,edge+1+m,cmp);
        for(int i=1;i<=m;i++){
            if(find(edge[i].u)==find(edge[i].v)) continue;
            join(edge[i].u,edge[i].v);
            ans=edge[i].w;
        }
        return ans;
    }
    void init(){
        for(int i=1;i<=n;i++) f[i]=i;
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++){
            cin>>x>>y>>w;
            edge[i].u=x,edge[i].v=y,edge[i].w=w;
        }
        cout<<n-1<<" "<<kruskal()<<'\n';
    }

**总结：**

**kruskal可以构造一棵完美最小生成树，即在构造的过程中生成的树的边权一定是所有边中最小的**

[1142. _ - AcWing]: https://www.acwing.com/problem/content/1144/
[6713fc4c4e764ab4a0cf4d5daabd9296.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a7f505f628ff4eaa9fa21042afd7104e.png