二分图普通匹配：匈牙利算法

  1. //P3386 【模板】二分图最大匹配
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int N = 510, M = 50010;
  5. //
  6. int tot = 0, ver[M], Head[N], Next[M];
  7. void addEdge(int u, int v) {
  8.     ver[++tot] = v;
  9.     Next[tot] = Head[u], Head[u] = tot;
  10. }
  11. //
  12. //如果点的下标从0开始，记得给match赋值为-1而不是0
  13. int vis[N], match[N];
  14. bool dfs(int u) {
  15.     for (int i = Head[u]; i; i = Next[i]) {
  16.         int v = ver[i];
  17.         if (!vis[v]) {
  18.             vis[v] = 1;
  19.             if (!match[v] || dfs(match[v])) {
  20.                 match[v] = u;
  21.                 return true;
  22.             }
  23.         }
  24.     }
  25.     return false;
  26. }
  27. //
  28. int n, m, e;
  29. int main()
  30. {
  31.     scanf("%d%d%d", &n, &m, &e);
  32.     for (int i = 0; i < e; ++i) {
  33.         int u, v;
  34.         scanf("%d%d", &u, &v);
  35.         //只连一条有向边即可
  36.         addEdge(u, v);
  37.     }
  38.     int ans = 0;
  39.     memset(match, 0, sizeof(match));
  40.     for (int i = 1; i <= n; ++i) {
  41.         memset(vis, 0, sizeof(vis));
  42.         ans += dfs(i);
  43.     }
  44.     printf("%d", ans);
  45.     return 0;
  46. }

匈牙利算法的时间戳优化

我们注意到，上面跑匈牙利的时候，每次都要 memset 一次，很烦，所以我们必须想办法进行优化。
我们不妨设置一个时间戳 now ，循环到第几个的时候就令时间戳为多少。在匈牙利内，改成这样：

//匈牙利部分
int now = 0;
int vis[N], match[N];
bool dfs(int u) {
    for (int i = Head[u]; i; i = Next[i]) {
        int v = ver[i];
        if (vis[v] != now) {
            vis[v] = now;
            if (!match[v] || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
//run
now = 0;
int ans = 0;
for (int i = 1; i <= n; ++i) {
    now++;
    if (!dfs(i)) ans++;
}

这样操作的正确性是显然的： vis[x]=now 就相当于以前的 vis[x]=1 ，而 vis[x]!=now 就相当于 vis[x]=0 。

二分图最大带权匹配

可见《算法竞赛进阶指南》
KM算法在稠密图上效率较高，优化空间大，但是只能够处理完备匹配的情况。
费用流比较通用，但是有时候数据比较大的时候会慢，甚至超时。

二分图最小带权匹配

将所有边权取反，即可转化为二分图最大匹配

基于 BFS 的 KM 算法

普通 KM 算法的最坏复杂度为 二分图 - 图1，数据过大的时候可能会超时，即使进行了其他诸如 slack优化之类的东西也不一定能通过 。
使用 BFS 进行优化后（不用多次建立交错树），可以将复杂度压到二分图 - 图2。

#define LL long long
const int N = 310;
#define INF ((1LL) << 61)
int n;
LL dis[N][N];
//求最大匹配的情况下，不存在的边赋值为-INF
//如果是求最小匹配，那么所有边的边权取负，那么不存在的边就会赋值为INF
//KM
int vis[N], match[N], pre[N];
LL la[N], ra[N], slack[N];
void bfs(LL u) {
    LL x, y = 0, yy = 0, delta;
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= n; i++)
        slack[i] = INF;
    match[y] = u;
    while (true) {
        x = match[y], delta = INF, vis[y] = 1;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            if (slack[i] > la[x] + ra[i] - dis[x][i]) {
                slack[i] = la[x] + ra[i] - dis[x][i];
                pre[i] = y;
            }
            if (slack[i] < delta)
                delta = slack[i], yy = i;
        }
        for (int i = 0; i <= n; i++)
            if (vis[i]) {
                la[match[i]] -= delta;
                ra[i] += delta;
            }
            else slack[i] -= delta;
        y = yy;
        if (match[y] == -1) break;
    }
    while (y) {
        match[y] = match[pre[y]];
        y = pre[y];
    }
}
LL KM()
{
    memset(match, -1, sizeof(match));
    memset(la, 0, sizeof(la));
    memset(ra, 0, sizeof(ra));
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        bfs(i);
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++)
        ans += dis[match[i]][i];
    return ans;
}