最小生成树（基础版）

· · 算法·理论

Part 1.什么是最小生成树

有一个问题：在一个无向图中，有 m 条边和 n 个节点，现在可以去掉一些边，使得这个图只剩下 n-1 条边切这还是个连通图，求只剩下 n-1 条边是所有边的权值的总和。

Part 2.kruskal

对于这个问题，我们可以对所有边的权值进行排序，挨个遍历每一条边，假设一开始没有任何的边，如果当前这一条边连接了一个没有任何一条边的点，那么连上这条边，更新答案，并将这个点标记为已连接。

由于需要判断当前节点是否在已生成的树中，所以要使用并查集。

kruskal 算法一般情况下时间复杂度为 O(m \log m)。

Part 3.Prim

Prim 算法采用了和 dijkstra 一样的“蓝白点思想”，初始时先将所有节点标记为未连接，然后选取未选择的最小边权的边，如果这个边连接了至少一个未连接的节点，那么更新答案，将这条边所连接的两个节点标记为已连接。

一般情况下，Prim 算法的时间复杂度为 O(m+n^2)

可以使用堆对其优化，堆优化后的 Prim 算法时间复杂度为 O(m)，但所用空间相对较多。

Prat 4.Boruvka

（此内容源自 OI Wiki）
Boruvka 算法可以看做是 Prim 算法和 kruskal 算法的结合体，它可以用来求解无向图的最小生成森林。

在边具有较多特殊性质的问题中，Boruvka 算法具有优势。

为了描述该算法，我们需要引入一些定义：

  1. 定义 E' 为我们当前找到的最小生成森林的边。在算法执行过程中，我们逐步向 E' 加边，定义 连通块 表示一个点集 V'\subseteq V，且这个点集中的任意两个点 u，v 在 E' 中的边构成的子图上是连通的（互相可达）。

    1. 定义一个连通块的 最小边 为它连向其它连通块的边中权值最小的那一条。

初始时，E'=\varnothing，每个点各自是一个连通块：

  1. 计算每个点分别属于哪个连通块。将每个连通块都设为「没有最小边」。

  2. 遍历每条边 (u, v)，如果 u 和 v 不在同一个连通块，就用这条边的边权分别更新 u 和 v 所在连通块的最小边。

  3. 如果所有连通块都没有最小边，退出程序，此时的 E' 就是原图最小生成森林的边集。否则，将每个有最小边的连通块的最小边加入 E'，返回第一步。

当原图连通时，每次迭代连通块数量至少减半，算法只会迭代不超过 O(\log V) 次，而原图不连通时相当于多个子问题，因此算法复杂度是 O(E\log V) 的。

Part 5.例题1

题目

何老板买了一栋别墅。这栋别墅总共有 N(2 \le N \le 1000) 个房间，何老板把他们编号为 1 到 N。何老板想给每个房间都牵上网线。他雇了一个电工来连网线。电工做了测量，这 N 个房间之间最多能连 M 条网线。每条网线都需要一定的花费 C(1 \le C \le 100000)。何老板想用最小的费用让所有房间都连上网络。

何老板经常拖欠农民工工资。之前好几次工作的工资何老板都还没发给这个电工。于是这个电工想报复何老板。这个电工决定做下面事情：

  1. 让何老板花的钱尽可能多。

  2. 让每个房间都连上网络（让何老板感觉他很好地完成了工作）。

  3. 让所有连线不构成环（如果有环会被何老板发现）。

问：电工最多让何老板花费多少？（若无法用网线将所有房间连接起来，就输出 -1）

解法

考虑使用 kruskal 算法，并查集，结构体存图，排序此处不再赘述。
定义一个数组存这个节点是否连接上了网络，然后判断当前节点是否已连上，如果不是，更新答案并将此节点标记为已连接。
参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,f[1005],cnt,a,b,c;
struct nide{
    int x,y,qian;
}lj[100005];
bool cmp(nide X,nide Y){
    return X.qian>Y.qian;
}
int getfather(int x){
    if(x!=f[x])f[x]=getfather(f[x]);
    return f[x];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        lj[++cnt].x=a;
        lj[cnt].y=b;
        lj[cnt].qian=c;
    }
    sort(lj+1,lj+1+cnt,cmp);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1,p=0;i<=cnt&&p<m-1;i++){
        int xx=getfather(lj[i].x);
        int yy=getfather(lj[i].y);
        if(xx!=yy){//如果当前边没连上网络
            p++;//当前已选边数加一
            ans+=lj[i].qian;//更新答案
            f[xx]=yy;//将此节点标记为已连接
        }
        if(p>=n-1){//如果选的边数够了，输出答案并结束程序
            printf("%d",ans);
            return 0;
        }
    }
    cout<<"-1";
    return 0;
}

Part 6.例题2

题目

国防部想要通过无线网络与北极地区的一些军事哨所建立通讯连接。有两种不同的通讯技术将要被用来建立这个网络系统：无线电和卫星电话。
每个哨所都将配置无线电收发器。只有部分哨所将配置卫星电话。任意两个配置了卫星电话的哨所可以通过卫星来通信，卫星通信不受地域和距离的限制。但是任意两个哨所想要通过无线电来通信的话，就有距离限制了，两者的距离不能超过 D 公里，这个距离 D 由无线电收发器的功率决定。无线电设备的功率越大，通信距离越远，但是价格也越高。处于价格和保养的考虑，国防部决定所有的哨所都使用相同的无线电收发器，也就是说每个哨所的无线电收发器的最大通信距离 D 都是相同的。 你的工作就是决定无线电设备的传输距离 D 最小应该是多少，才能保证任意两个哨所间都有直接或间接的通信线路可以通信。

输入格式
第一行两个整数 S 和 P，S 表示可供使用的卫星电话的数量,P 表示哨所的数量。 接下来 P 行，每行两个整数 X 和 Y，表示一个哨所的位置坐标，单位是公里。

解法

首先这个题只告诉了我们每个哨所的坐标，所以需要我们用勾股定理来计算每两个哨所之间最短的距离（直线距离），接下来考虑使用 kruskal 算法，但是有一个值得注意的地方，在这个题中，所有的哨所都可以使用卫星电话，卫星电话有 S 个，即其中的 S 个哨所可以没有能通信的线路（有一个卫星电话应该在算出来的最小生成树的节点中）。

代码

#include<bits/stdc++.h>
using namespace std;
struct lilaoshi{
    long long x,y;
    double qian;
}a[2500005];
long long f[5000005],n,m,k,cnt,p,A[5000005],B[5000005];
double ans;
long long zhaobaba(long long xx){
    if(xx!=f[xx])f[xx]=zhaobaba(f[xx]);
    return f[xx];
}
bool cmp(lilaoshi X,lilaoshi Y){
    return X.qian<Y.qian;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=m;i++)f[i]=i;
    for(long long i=1;i<=m;i++)scanf("%lld%lld",&A[i],&B[i]);
    for(long long i=1;i<m;i++){
        for(long long j=i+1;j<=m;j++){
            a[++cnt].x=i;
            a[cnt].y=j;
            //勾股定理求距离
            a[cnt].qian=sqrt((A[i]-A[j])*(A[i]-A[j])+(B[i]-B[j])*(B[i]-B[j]));
        }
    }
    sort(a+1,a+1+cnt,cmp);
    for(long long i=1;i<=cnt;i++){
        long long fx=zhaobaba(a[i].x);
        long long fy=zhaobaba(a[i].y);
        if(fx!=fy){
            p++;
            ans=max(ans,a[i].qian);
            f[fx]=fy;
        }
        if(p==m-n)break;
        //剩下的哨所用卫星电话，不需要通信线路
    }
    printf("%.2lf",ans);
    return 0;
}

完结撒花！

（如果你还不懂，就评论区见吧）