二分图匹配（匈牙利算法）NOI

💡 核心思想

匈牙利算法用于求解二分图的最大匹配问题。核心思想是"增广路"：如果当前点未匹配，则尝试匹配；如果已匹配，则尝试让已匹配的点换个对象，腾出位置给当前点。通过 DFS 寻找增广路，每找到一条增广路，匹配数就加 1。

🎯 直觉理解

匈牙利算法解决二分图最大匹配：左边一群男生、右边一群女生，互有好感的连线，最多能凑成几对？

思想是"腾位置"：给一个男生找对象时，如果心仪的女生已经有主，就试着让那个女生现在的对象换个女生——这串"换"的过程叫找增广路。每找到一条增广路，匹配数就加 1。

实现：DFS 依次给每个左侧点找匹配，用 vis 标记本次尝试访问过的右侧点（防死循环），match 数组记录右侧点现在配对的左侧点。没有增广路时匹配数最大——这个结论保证算法正确。

📝 算法流程

1. 初始化 match[] 数组为 0（未匹配）
2. 对于每个左侧节点 u：
3. 清空 vis 标记
4. DFS 寻找增广路：遍历 u 的所有邻接点 v
5. 如果 v 未访问且（v 未匹配 或 match[v] 能找到新的匹配）
6. 则 match[v] = u，返回 true
7. 如果找不到增广路，u 暂时无法匹配
8. 答案为成功匹配的对数

$$\text{最大匹配数} = \text{最小点覆盖数} = |V| - \text{最大独立集数} \quad \text{（König 定理）}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

const int N = 505;
vector g[N]; // 左侧点 u 的邻接表（右侧点 v）
int match[N];     // 右侧点 v 匹配的左侧点
bool vis[N];

bool dfs(int u) {
    for (int v : g[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (match[v] == 0 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian(int nLeft) {
    int res = 0;
    for (int u = 1; u <= nLeft; u++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(u)) res++;
    }
    return res;
}

int main() {
    int n = 3, m = 3;
    g[1].push_back(1); g[1].push_back(2);
    g[2].push_back(2); g[2].push_back(3);
    g[3].push_back(1); g[3].push_back(3);
    cout << hungarian(n) << endl; // 3
    return 0;
}

⚠️ 常见坑点

📚 相关题目