二分图

二分图匹配

二分图：把无向图 G = （V，E）分为两个集合 V1，V2，所有的边都在 V1 和 V2 之间，而 V1 或 V2 的内部没有边。V1 中的一个点与 V2 中的一个点关联，称为匹配。
染色法：一个图是否为二分图，一般用“染色法”进行判断。用两种颜色对所有顶点进行染色，要求一条边所连接的两个相邻顶点的颜色不相同。染色结束后，如果所有相邻顶点的颜色都不相同，它就是二分图。
结论：一个图是二分图，当且仅当它不含边的数量为奇数的圈。

二分图最大匹配问题

二分图最大匹配问题：无权图，求包含边数最多的匹配，即二分图的最大匹配。
图片说明

匈牙利算法

时间复杂度: $图片说明$
匈牙利算法可以看成最大流的一个特殊实现。
由于二分图是一个很简单的图，并不需要做一个标准的最大流，可以进行简化。

从上面的图解中发现对 s 和 t 的操作是多余的，直接从 a、b、c 开始找增广路径就可以了。
残留网络上的增广路需要覆盖完整的路径，如果在二分图中进行{a、b、c}到{x、y、z}的局部操作，将之用一个数组match[]就有覆盖整个路径的效果。

// 络谷 板子题（https://www.luogu.com.cn/problem/P3386）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 501;
const int maxm = 5e4+1;

struct edge{
    int to, next;
}e[maxm<<1]; int head[maxn], tot;
int match[maxn];
bool vis[maxn];

void addedge(int u, int v) {
    e[++tot] = {v, head[u]}, head[u] = tot;
}

int dfs(int x) {
    for(int i = head[x]; ~i; i = e[i].next) {
        int j = e[i].to;
        if (vis[j]) continue;
        vis[j] = true;
        if (!match[j] || dfs(match[j])) {
            match[j] = x;
            return 1;
        }
    }
    return 0;
}

int main() {
    int nx, ny, m; scanf("%d%d%d", &nx, &ny, &m);
    memset(head, -1, sizeof head), tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v; scanf("%d%d", &u, &v);
        addedge(u, v);
    }
    int maxmatch = 0;
    for(int i = 1; i <= nx; ++ i) {
        memset(vis, false, sizeof vis);
        maxmatch += dfs(i);
    }
    printf("%d\n", maxmatch);
    return 0;
}

Hopcroft-Krap算法

时间复杂度： $图片说明$
预先找到多条路径最短的增广路，然后匈牙利算法就沿着bfs找的路径去找增广路。
bfs具体步骤：

把 V1 中所有没匹配的点加入队列
每次出来一个点 x，对于它连的 V2 中的每个点 y，如果 y 没访问过且没匹配过，找到增广路，否则把 y 的匹配点压入队列

// hdu 2063 （http://acm.hdu.edu.cn/showproblem.php?pid=2063）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 501;
const int inf = 0x3f3f3f3f;

vector<int> g[maxn];
int cx[maxn], cy[maxn];
int dx[maxn], dy[maxn];
int vis[maxn];

int bfs(int n) { // bfs搜索多条不想交最短增广路径
    memset(dx, 0, sizeof(dx));
    memset(dy, 0, sizeof(dy));
    queue<int> q;
    for(int i = 1; i <= n; ++ i) {
        if (!cx[i]) q.push(i);
    }
    int dis = inf;
    while(!q.empty()) {
        int t = q.front(); q.pop();
        if (dx[t] >= dis) continue;
        for(auto i: g[t]) {
            if (dy[i]) continue;  // 多条路径不想交
            dy[i] = dx[t] + 1;
            if (!cy[i]) dis = dy[i]; // 最短路径已找到
            else {
                dx[cy[i]] = dy[i];
                q.push(cy[i]);
            }
        }
    }
    return dis != inf;
}

int dfs(int x) {   // 按照bfs搜索路径进行dfs
    for(auto i: g[x]) {
        if (vis[i] || dy[i] != dx[x] + 1) continue;
        vis[i] = 1;
        if (!cy[i] || dfs(cy[i])) {
            cx[x] = i, cy[i] = x;
            return 1;
        }
    }
    return 0;
}

int HK(int n) { // HK算法
    memset(cx, 0, sizeof(cx));
    memset(cy, 0, sizeof(cy));
    int res = 0;
    while(bfs(n)) {
        memset(vis, 0, sizeof(vis));  // 模拟dy[] 保证路径不相交
        for(int i = 1; i <= n; ++ i) {
            if (!cx[i] && dfs(i)) res ++;
        }
    }
    return res;
}

int main() {
    int n; while(scanf("%d", &n), n) {
        int x, y; scanf("%d%d", &x, &y);
        for(int i = 1; i <= x; ++ i) g[i].clear();
        for(int i = 1; i <= n; ++ i) {
            int u, v; scanf("%d%d", &u, &v);
            g[u].push_back(v);
        }
        printf("%d\n", HK(x));
    }
    return 0;
}

Dinic 算法

用网络流来写二分图最大匹配。

// 络谷 板子题（https://www.luogu.com.cn/problem/P3386）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 5010 << 1;
const int maxm = 5e4 + maxn;

struct edge{
    int to, next, cap, flow;
}e[maxm<<2]; int head[maxn], tot;
int nx, ny, m, s, t, d[maxn], cur[maxn];

void addedge(int u, int v, int w) {
    e[++tot] = {v, head[u], 1, 0}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0}, head[v] = tot;
}

void init() { // 连接源点 和 汇点
    memset(head, -1, sizeof head);
    tot = -1;
    s = nx + ny + 1;
    for(int i = 1; i <= nx; ++ i) {
        addedge(s, i, 1);
    }
    t = nx + ny + 2;
    for(int i = 1; i <= ny; ++ i) {
        addedge(i + nx, t, 1);
    }
}

bool bfs() {
    memset(d, 0x7f, sizeof d);
    queue<int> q; q.push(t);
    d[t] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (d[j] > d[x] + 1 && e[i^1].cap > e[i^1].flow) {
                d[j] = d[x] + 1;
                if (j == s) return true;
                q.push(j);
            }
        }
    }
    return false;
}

int dfs(int x, int flow, int used = 0) {
    if (x == t) return flow;
//    for(int i = cur[x]; ~i && flow != used; i = e[ cur[x] = i ].next) { // 当前弧优化
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        int j = e[i].to, f;
        if (d[x] - 1 == d[j] && e[i].cap > e[i].flow) {
            f = dfs(j, min(flow - used, e[i].cap - e[i].flow));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    if (!used) d[x] = 0; // 剪枝优化
    return used;
}

int main() {
    scanf("%d%d%d", &nx, &ny, &m);
    init();
    for(int i = 1; i <= m; ++ i) {
        int u, v; scanf("%d%d", &u, &v);
        addedge(u, v + nx, 1);
    }
    int maxflow = 0;
    while(bfs()) {
//        memcpy(cur, head, sizeof head);
        maxflow += dfs(s, INT_MAX);
    }
    printf("%d\n", maxflow);
    return 0;
}

二分图求最大权匹配

KM 算法

时间复杂度： $图片说明$
KM算法：用于求二分图匹配的最佳匹配（最大权完美匹配）。
算法过程：

用邻接矩阵存图，给每个点加一个期望（cx[] 或 cy[]），当一对匹配的期望和等于其权值时该匹配才有可能匹配，我们需要最大权值和，所以先假设期望可以最大 cx[i] = max{与它有关的匹配权值}，cy[i] = 0。
尝试对第 i 个点进行匹配，若匹配成功，则进行下一个；若匹配失败，则降低左边已匹配点和该点的期望，提高右边已匹配点的期望，通过降低期望的方式尝试与独立点进行匹配，重复操作2。

注：初始化各点期望后，实线为可能匹配，虚线暂时不能匹配。（绿色为匹配成功，黄色为增广路，红色为匹配失败）
图片说明
注：若经过图四修改后 x2 仍然匹配失败，则重复图四修改即可。

注：代码中 km算法是完备匹配下的最大期望，若初始化为0，则是最大权值和。

// hdu 2255 （http://acm.hdu.edu.cn/showproblem.php?pid=2255）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 301;

int graph[maxn][maxn];
int match[maxn], hx[maxn], hy[maxn], d[maxn], pre[maxn];
bool vis[maxn];

int km(int n) {
    memset(match, 0, sizeof match);
    for(int i = 1; i <= n; ++ i) { // 初始化期望权值
        hx[i] = INT_MIN, hy[i] = 0;
        for(int j = 1; j <= n; ++ j) {
            hx[i] = max(graph[i][j], hx[i]);
        }
    }
    for(int i = 1; i <= n; ++ i) {  // 尝试匹配
        memset(d, 0x7f, sizeof d);
        memset(vis, false, sizeof vis);
        int pos = 0, y;
        match[pos] = i;
        do {   // 通过不段提高期望来满足匹配
            int dis = INT_MAX, x = match[pos];
            vis[pos] = true;
            for(int j = 1; j <= n; ++ j) {
                if (vis[j]) continue;
                if (d[j] > hx[x] + hy[j] - graph[x][j]) {
                    d[j] = hx[x] + hy[j] - graph[x][j];
                    pre[j] = pos;
                }
                if (dis > d[j]) {
                    dis = d[j];
                    y = j;
                }
            }
            for(int j = 0; j <= n; ++ j) {
                if (vis[j]) hx[ match[j] ] -= dis, hy[j] += dis;
                else d[j] -= dis;
            }
            pos = y;
        } while(match[pos]);
        for(int j = pos; j; j = pre[j]) {
            match[j] = match[ pre[j] ];
        }
    }
    int res = 0;
    for(int i = 1; i <= n; ++ i) {
        res += graph[ match[i] ][i];
    }
    return res;
}

int main() {
    int n; while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++ i) {
            for(int j = 1; j <= n; ++ j) {
                scanf("%d", &graph[i][j]);
            }
        }
        printf("%d\n", km(n));
    }
    return 0;
}