二分图最大权完美匹配：KM算法

KM算法只适用于一定存在完美匹配的情形。

洛谷P6577 【模板】二分图最大权完美匹配

题目描述

给定一张二分图，左右部均有 n 个点，共有 m 条带权边，且保证有完美匹配。
求一种完美匹配的方案，使得最终匹配边的边权之和最大。

输入格式

第一行两个整数 n,m；第 2\sim m+1 行，每行三个整数 y,c,h 描述了图中的一条从左部的 y 号结点到右部的 c 号节点，边权为 h 的边。

输出格式

第一行一个整数 ans 表示答案；第二行共 n 个整数 a_1,a_2,a_3\cdots a_n，其中 a_i 表示完美匹配下与右部第 i 个点相匹配的左部点的编号。

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int INF = 1e9;

struct KM {
    int w[N][N], lx[N], ly[N];
    int slack[N];
    int linker[N], pre[N];
    int n;
    bool vis[N];
    void init(int n) {
        this->n = n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                w[i][j] = -INF;
            }
        }
    }
    void bfs(int x) {
        int y = 0, nex = 0;
        int d;
        for (int i = 1; i <= n; i++) {
            pre[i] = 0;
            vis[i] = false;
            slack[i] = INF;
        }
        linker[y] = x;
        while (true) {
            x = linker[y]; d = INF; vis[y] = true;
            for (int i = 1; i <= n; i++) {
                if (!vis[i]) {
                    if (slack[i] > lx[x] + ly[i] - w[x][i]) {
                        slack[i] = lx[x] + ly[i] - w[x][i];
                        pre[i] = y;
                    }
                    if (slack[i] < d) {
                        d = slack[i];
                        nex = i;
                    }
                }
            }
            for (int i = 0; i <= n; i++) {
                if (vis[i]) {
                    lx[linker[i]] -= d;
                    ly[i] += d;
                }
                else slack[i] -= d;
            }
            y = nex;
            if (linker[y] == -1) break;
        }
        while(y) {
            linker[y] = linker[pre[y]];
            y = pre[y];
        }
    }
    long long solve() {
        long long rs = 0;
        for (int i = 1; i <= n; i++) {
            lx[i] = ly[i] = 0;
            linker[i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            bfs(i);
        }
        for (int i = 1; i <= n; i++) {
            rs += lx[i] + ly[i];
        }
        return rs;
    }
}km;

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    km.init(n);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        km.w[u][v] = w;
    }
    printf("%lld\n", km.solve());
    for (int i = 1; i <= n; i++) {
        printf("%d%c", km.linker[i], i == n ? '\n' : ' ');
    }
    return 0;
}

应用举例（用于树形dp转移）：
2020牛客多校第十场 J. Identical Trees

二分图最大权最佳匹配：费用流算法

套用费用流模版，从源点向左边点连权值为 1、花费为 0 的边；从左边点向右边点连权值为 1、花费为 -cost 的边；从右边点向汇点连权值为 1、花费为 0 的边。
跑出最小费用最大流后，对最小费用取相反数即为答案。

int main() {
    scanf("%d%d", &n, &m);
    S = n + n + 1; T = S + 1;
    mcmf.init(T, S, T);
    for (int i = 1; i <= n; i++) {
        add(S, i, 1, 0);
        add(i + n, T, 1, 0);
    }
    for(int i = 1, a, b, c; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b + n, 1, -c);
    }
    mcmf.solve();
    printf("%lld\n", -mcmf.mincost);
}