二分图匹配（匈牙利算法）CSP-S

💡 核心思想

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

🎯 直觉理解

想象你在组织一场联谊活动，左边是男生，右边是女生，边表示两人互相有好感。匈牙利算法就像一个"热心红娘"：遇到一个男生，先给他介绍一个女生；如果这个女生已经有对象了，就去找那个女生的对象，问他能不能换个女生；如果能换，就皆大欢喜；如果不能，就继续找人换...直到所有人都尽力了。

📝 算法流程

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;
}

⚠️ 常见坑点

📚 相关题目