最小生成树

Prim 算法

(稀疏图)
朴素版Prim O(n^2)
堆优化版Prim O(mlogn)

Kruskal 算法

(稠密图)
O(mlogm)

二分图

染色法

O(n+m)

匈牙利算法

O(mn),实际运行时间一般远小于O(mn)

朴素版Prim 算法

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

using namespace std;
const int N = 510, INF = 0x3f3f3f3f;

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

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    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 || dist[t] > dist[j]))
                t = j;

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

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

    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);

    cin >> 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 printf("%d\n", t);

    return 0; 
}

Kruskal 算法
并查集 ( acwing837 )

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

using namespace std;
const int N = 2e5 + 10;

int n, m;
int p[N];

struct Edge{
    int a, b, w;
}edges[N];

bool cmp(Edge A, Edge B)
{
    return A.w < B.w;
}

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

int main()
{
    cin >> n >> m;

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

    sort(edges, edges + m, cmp);

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

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;


        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }

    if (cnt < n - 1) puts("impossible");
    else printf("%d\n", res);

    return 0;
}

染色法
二分图当且仅当图中不含奇数环

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

using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int c)
{
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }

    if (flag) puts("Yes");
    else puts("No");

    return 0;
}

匈牙利算法

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

using namespace std;
const int N = 1e5 + 10;

int n1, n2, m;
int h[N], e[N], ne[N], idx;
int match[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;

        st[j] = true;

        if (!match[j] || find(match[j]))
        {
            match[j] = x;
            return true;
        }
    }

    return false;
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n1 >> n2 >> m;

    while (m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    int res = 0;
    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, false, sizeof st);
        if (find(i)) res ++;
    }

    cout << res << endl;

    return 0;
}