最小生成树模板

最小生成树也是图论中的一类问题。最小生成树问题最终要求出使所有点连通的最短距离，典型问题为修公路问题。

Prim算法

适合稠密图

思路

Prim算法与Dijkstra算法有很多相似之处。
1. 初始化距离，与Dijkstra算法不同的是Prim算法要将所有点的距离初始化正无穷。
2. 循环n次 
    每一次找到不在生成树中距离最小的点（这里的距离指的是距离集合的距离而Dijkstra指的是到一号点的距离）
    再用这个点更新临界点的距离。

时间复杂度

具体题目

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

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int g[N][N], dist[N];
bool st[N];

int n, m, res;

int prim()
{
    memset(dist, 0x3f, sizeof(dist));
    // 循环n次
    for(int i = 0; i < n; i++)
    {   
        // 寻找集合以外距离最小的点
        int t = -1;
        for(int j = 1; j <= n; j++)
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;
        
        // 如果这个点不是第一个点并且距离最短的点为正无穷 则不连通 直接返回false
        if (i && dist[t] == INF) return INF;
        // 如果这个点不是第一个点则加到最终的答案中
        if (i) res += dist[t];

        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if (i == j) g[i][j] = 0;
            else g[i][j] = INF;

    while (m--)
    {
        int x, y, c;   
        scanf("%d%d%d", &x, &y, &c);
        g[x][y] = g[y][x] = min(g[x][y], c);
    }

    int ret = prim();

    if(ret == INF) puts("impossible");
    else cout << ret;

    return 0;
}

Kruskal算法

思路

1. 排序
    将所有的边按照权重排序
2. 遍历所有的边 a->b 权重为 w
    如果 a b 不在同一个集合 则合并 考察并查集的知识

时间复杂度

主要在排序的过程：O(mlogm)

具体题目

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

using namespace std;

const int N = 100010, M = 200010;

// 因为只需遍历所有的边所以可以用一个简单的结构体数组，来存储边

struct Edge
{
    int x, y, c;

    // 运算符重载 据我的我猜测sort内部实现的时候用的是 < 然后结构体不是基本数据类型 所以要重载
    // c++中 class与struct 定义类可以互换 只是 在默认情况下 struct为public class为private
    // 这个东西估计要看侯捷的《STL源码剖析》吧。
    bool operator< (const Edge &obj) const
    {
        return c < obj.c;
    }
}edges[M];

int p[N];

int n, m, cnt, res;

int find(int x)
{
    // 路径压缩
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

bool kruskal()
{
    sort(edges, edges + m);

    // 初始化并查集
    for(int i = 1; i <= n; i++)
        p[i] = i;

    for(int i = 0; i < m; i++)
    {
        int x = edges[i].x, y = edges[i].y, c = edges[i].c;
        int a = find(x), b = find(y);
        if(a != b)
        {
            p[a] = b;
            res += c;
            cnt++;
        }
    }
    if(cnt < n - 1) return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        //edges[i] = {x, y, c}; c11
        edges[i].x = x;
        edges[i].y = y;
        edges[i].c = c;
    }

    if(kruskal()) cout << res << endl;
    else puts("impossible");
    
    return 0;
}