最小生成树

1. 普利姆算法（Prim）
   1. 朴素版Prim 适用于稠密图 O(n^2)
   2. 堆优化版Prim 适用于稀疏图 O(mlogn)
2. 克鲁斯卡尔算法（kruskal） 适用于稀疏图 O(mlogm)

朴素版Prim算法

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

using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], d[N];
int n, m;
bool st[N];

int prim()
{
    memset(d, 0x3f, sizeof d);
    int res = 0;

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
        {
            if(!st[j] &&(t == -1 || d[t] > d[j]))
                t = j;
        }

        if(i && d[t] == INF) return INF;
        if(i) res += d[t];
        st[t] = true;

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

int main()
{
    memset(g, 0x3f, sizeof g);
    scanf("%d%d", &n, &m);

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

    int t = prim();
    if(t == INF) puts("impossible");
    else cout << t << endl;

    return 0;
}

Kruskal算法

1. 将所有边按权重从小到大排序 O(mlogm)
2. 枚举每条边
   1. 如果不连通，则将这条边加入集合中

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

using namespace std;
const int N = 200010;
struct Edge{
    int a, b, c;

    bool operator< (const Edge &W)const
    {
        return c < W.c;
    }
}edges[N];
int p[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    sort(edges, edges + m);

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, c = edges[i].c;
        a = find(a), b = find(b);
        if(a != b)
        {
            cnt ++;
            res += c;
            p[a] = b;
        }
    }

    if(cnt != n - 1) puts("impossible");
    else cout << res << endl;
    return 0;
}

二分图

1. 染色法 O(n + m)
2. 匈牙利算法（也叫绿帽算法XD） O(mn)，实际运行时间一般远小于O(mn)