54 · 二分图与匈牙利算法

二分图是图论里结构最干净的一类：点能分成左右两堆，每条边都从左边连到右边，堆内没有边。结构干净，问题就好算——“把 n 个任务分给 m 个人，每人最多一个、每人只会其中几项”，这类分配问题一旦建成二分图，就变成了求最大匹配。

先解决“怎么知道它是不是二分图”。做法就是把二分图的定义直接翻译成代码：任选一个点染成 0，它的邻居全染成 1，邻居的邻居再染回 0……如果某条边的两端被迫同色，这个图就不是二分图。

int col[10005];

// 对 s 所在的连通块染色，冲突返回 false
bool paint(int s) {
    queue<int> q;
    q.push(s);
    col[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (col[v] == -1) { col[v] = col[u] ^ 1; q.push(v); }
            else if (col[v] == col[u]) return false;   // 同色相邻
        }
    }
    return true;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 10005;
const int M = 100005;

int head[N], nxt[M << 1], to[M << 1], ecnt;
int col[N];                             // -1 未染色，0 / 1 两种颜色

void addEdge(int u, int v) {
    to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
}

// 对 s 所在连通块染色；能二染色返回 true
bool paint(int s) {
    queue<int> q;
    q.push(s);
    col[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (col[v] == -1) {                  // 没染过：染成相反色
                col[v] = col[u] ^ 1;
                q.push(v);
            } else if (col[v] == col[u]) {       // 同一条边两端同色 → 存在奇环
                return false;
            }
        }
    }
    return true;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        addEdge(u, v); addEdge(v, u);            // 无向边，存两份
    }

    memset(col, -1, sizeof col);                 // ★ 必须先置 -1
    for (int i = 1; i <= n; ++i) {               // 图可能不连通，每块各开一次
        if (col[i] != -1) continue;
        if (!paint(i)) { printf("No\n"); return 0; }
    }
    printf("Yes\n");
    return 0;
}

判定解决“结构对不对”，匹配解决“怎么配最多”。下面这道模板题把问题剥到最干净：给一个二分图和若干条允许的配对，问最多能配出几对。

对每个左侧点 u：
    vis[1..m] = false                    // 本轮尝试重新开始
    dfs(u)：
        for u 的每个邻点 v：
            if vis[v]: continue          // 本轮试过了，跳过（否则绕圈）
            vis[v] = true
            if match[v] == 0             // v 空着：直接配
               或 dfs(match[v])          // v 有主人：让主人另找出路
                match[v] = u; return true
        return false                     // 所有出路都被堵死

int match[505];                        // 右侧最多 500 个点

// 匹配成功后：
//   match[R1] = L2   R1 现在归 L2
//   match[R2] = L1   R2 现在归 L1
// 未匹配的右侧点：match[R3] == 0

// 输出方案（左侧 u 与右侧 v 配对，v 从 1 到 m）
for (int v = 1; v <= m; ++v)
    if (match[v]) printf("%d %d\n", match[v], v);

bool dfs(int u) {
    for (int e = head[u]; e; e = nxt[e]) {     // 遍历 u 的所有候选
        int v = to[e];
        if (vis[v]) continue;                  // 本轮试过了
        vis[v] = true;
        if (match[v] == 0 || dfs(match[v])) {  // v 空着，或原配能让位
            match[v] = u;                      // 翻转这条路上的最后一条边
            return true;
        }
    }
    return false;
}

#include <bits/stdc++.h>
using namespace std;

const int NL = 505;                     // 左侧点数上限
const int NR = 505;                     // 右侧点数上限
const int ME = 100005;                  // 边数上限（题给 5×10^4，留一倍余量）

int head[NL], nxt[ME], to[ME], ecnt;
int match[NR];                          // match[v]：右侧点 v 配给的左侧点，0 表示空
bool vis[NR];                           // 本轮 dfs 中右侧点是否试过

void addEdge(int u, int v) {
    to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
}

bool dfs(int u) {
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (vis[v]) continue;                    // 本轮试过，跳过（防绕圈）
        vis[v] = true;                           // 先标记，成功失败都不再试
        if (match[v] == 0 || dfs(match[v])) {    // v 空着，或原配能另找出路
            match[v] = u;                        // 接手 v
            return true;
        }
    }
    return false;                                // 所有候选都被堵死
}

int main() {
    int n, m, e;
    scanf("%d %d %d", &n, &m, &e);
    for (int i = 1; i <= e; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        addEdge(u, v);                           // 只存左侧 -> 右侧的单向边
    }

    int ans = 0;
    for (int u = 1; u <= n; ++u) {               // 每个左侧点各发起一次尝试
        memset(vis, 0, sizeof vis);              // ★ 新一轮必须重新清空
        if (dfs(u)) ++ans;                       // 找到增广路，匹配数恰好 +1
    }
    printf("%d\n", ans);
    return 0;
}

匹配算完之后，二分图上还有两个量和它死死绑定。它们不需要额外算法，只要知道定理，就是一次加减法。

#include <bits/stdc++.h>
using namespace std;

const int N = 10005;
const int M = 100005;

int head[N], nxt[M << 1], to[M << 1], ecnt;
int col[N];                             // -1 未染色，0 / 1 两种颜色
int cnt[2];                             // 当前连通块里两种颜色的点数

void addEdge(int u, int v) {
    to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
}

// 对 s 所在连通块染色，同时统计两种颜色各多少个；出现奇环返回 false
bool paint(int s) {
    queue<int> q;
    q.push(s);
    col[s] = 0;
    cnt[0] = cnt[1] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ++cnt[col[u]];                       // 出队时统计，每个点只算一次
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (col[v] == -1) { col[v] = col[u] ^ 1; q.push(v); }
            else if (col[v] == col[u]) return false;   // 同色相邻 → 奇环
        }
    }
    return true;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        addEdge(u, v); addEdge(v, u);         // 双向道路，存两份
    }

    memset(col, -1, sizeof col);              // ★ 未染色必须是 -1
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (col[i] != -1) continue;            // 已在别的连通块里染过
        if (!paint(i)) { printf("Impossible\n"); return 0; }
        ans += min(cnt[0], cnt[1]);            // 两种染色方案，取更省的那个
    }
    printf("%d\n", ans);
    return 0;
}