题解：【模板】最小生成树 [生成树]

· · 题解

Solution 【模板】最小生成树

题面

传送门： https://www.luogu.com.cn/problem/P3366

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

思路

Prim 算法：

算法介绍

Prim 和 Dijkstra 算法很像，是以任意节点开始搜索，再循环找出与之相邻的所有边，存（此题中为累加）最短距离，再以最短边的另一个端点继续遍历边，继续累加。

正确性证明

证明：对于任意一个顶点 u，连接到该顶点的所有边中的一条最短边 ({u,u_i}) 必然属于最小生成树。

即任意一个属于最小生成树的连通子图，从外部连接到该连通子图的所有边中的一条最短边必然属于最小生成树。

由最小生成树的定义（联通所有边并且边权和最小）可以推出。

复杂度说明

时间复杂度：O(n^2 + m)，O(n^2) 来自遍历点，O(m) 来自访问边。

Kruskal 算法：

算法介绍

Kruskal 算法先把边按照权值进行排序，优先选取权值较小的边，并累加权值，若出现环则跳过此边（用并查集来判断是否存在环）继续搜，直到所有边恰好将每个点连接（比总点数少一）即可。

正确性证明

证明：由最小生成树的定义（联通所有边并且边权和最小）可知：所有能够连接任意两个点的边中的最短的那条边必然属于最小生成树，所以这个算法也是正确的。

复杂度说明

时间复杂度：用堆优化是 O(m \log{m})，其中 O(m \log{m}) 来自排序，O(m \log{n}) 来自并查集。

并查集可参考：https://www.luogu.com.cn/article/hsqoa43y

注意事项

  1. 数组大小要合适。
  2. 初始化。
  3. 该开 long long 就开。
  4. 不连通要特判。

代码

Prim 代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long p,ans;
int u,v,w;
int vis[1145141],dis[1145141],a[5005][5005];
int prim(int k) {
    dis[k]=0;
    for(int i=1; i<=n; i++) {
        int t=-1;
        for(int j=1; j<=n; j++) {
            if(!vis[j]&&(t==-1||dis[j]<dis[t])) {
                t=j;
            }
        }
        if(dis[t]>=0x3f3f3f3f) {
            return 0x3f3f3f3f;//不连通 
        }
        ans+=dis[t];
        vis[t]=1;
        for(int j=1; j<=n; j++) {
            if(!vis[j]) {
                dis[j]=min(dis[j],a[t][j]);
            }
        }
    }
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);

    for(int i=0; i<5005; i++) {
        for(int j=0; j<5005; j++) {
            a[i][j]=0x3f3f3f3f;
        }
        dis[i]=0x3f3f3f3f;
    }
    memset(a,127,sizeof(a));
    memset(dis,127,sizeof(dis));
    //初始化 
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d",&u,&v,&w);
        a[u][v]=min(a[u][v],w);
        a[v][u]=min(a[v][u],w);
    }
    p=prim(1);
    if(p==0x3f3f3f3f) {
        cout<<"orz";
    } else {
        printf("%lld",p);
    }
    return 0;
}

Kruskal 代码实现

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,x,y,z,ans;
long long fa[1145141];
struct node {
    int x,y,v;
    friend bool operator < (node a,node b) {
        return a.v > b.v;//从小到大排序，让小的排在前面。 
    }
};
node a[1145141];
priority_queue<node> q;
int find(int x) {
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        fa[i]=i;
    }
    for(int i=1; i<=m; i++) {
        cin>>a[i].x>>a[i].y>>a[i].v;
        q.push(a[i]);
    }
    for(int i=1; i<=m; i++) {
        x=q.top().x,y=q.top().y,z=q.top().v;
        q.pop();
        if(find(x)!=find(y)) {
            ans+=z;
            t++;
            fa[find(y)]=find(x);
        }
        if(t==n-1) {
            break;
        }
    }
    if(t<n-1)cout<<"orz";
    else cout<<ans;
    return 0;
}