二分图最大匹配题解

题目概述

这道题目要求我们计算一个二分图的最大匹配边数。二分图是指顶点可以分成两个不相交的集合，使得每条边的两个端点分别属于这两个集合。最大匹配是指在二分图中找到尽可能多的边，使得这些边没有共同的顶点。

算法思路

本题采用匈牙利算法来解决二分图最大匹配问题。匈牙利算法的基本思想是通过不断寻找增广路径来增加匹配的边数。

关键步骤

图的构建：使用邻接表存储二分图的边关系。

匹配过程：对于左部的每一个顶点，尝试在右部找到一个未匹配的顶点或者能够"腾出"位置的顶点。

增广路径：通过深度优先搜索(DFS)寻找增广路径，如果找到则增加匹配数。

代码解析

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

int n, m, k, a, b, ans;
struct node {
    int v, ne; // v表示边的终点，ne表示下一条边的索引
}e[100005];
int h[100005], idx; // h数组存储每个顶点的第一条边，idx是边的计数器
int vis[100005], match[100005]; // vis记录访问状态，match记录右部顶点的匹配

// 添加边
void add(int a, int b) {
    e[++idx] = {b, h[a]};
    h[a] = idx;
}

// 匈牙利算法核心DFS函数
bool dfs(int u) {
    for (int i = h[u]; i; i = e[i].ne) {
        int v = e[i].v;
        if (vis[v]) continue; // 如果已经访问过则跳过
        vis[v] = 1;
        // 如果右部顶点未匹配，或者可以找到增广路径
        if (!match[v] || dfs(match[v])) {
            match[v] = u; // 更新匹配
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        cin >> a >> b;
        add(a, b); // 添加边
    }
    
    // 对每个左部顶点尝试匹配
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis)); // 每次匹配前重置访问状态
        if (dfs(i)) ans++; // 如果找到匹配则增加计数
    }
    
    cout << ans << endl;
    return 0;
}

复杂度分析

时间复杂度：O(n*e)，其中n是左部顶点数，e是边数。对于每个左部顶点，最坏情况下需要遍历所有边。

空间复杂度：O(n+m+e)，用于存储图结构和匹配信息。

优化建议

对于大规模数据，可以考虑更高效的算法如Hopcroft-Karp算法，其时间复杂度为O(e√n)。

可以使用更高效的图表示方法，如前向星等。

总结

匈牙利算法是解决二分图匹配问题的经典算法，虽然在最坏情况下时间复杂度较高，但对于题目给定的数据规模(1≤n,m≤500)是完全可行的。理解并掌握这一算法对于解决图论中的匹配问题非常重要