题解：P3386 【模板】二分图最大匹配

changxiang2012 · 2025-05-18 15:17:18 · 题解

二分图最大匹配问题题解

二分图最大匹配是图论中的经典问题，这类问题在资源分配、任务调度等场景中有广泛应用。本次我们通过匈牙利算法来解决这个问题。

问题分析

题目给出的是一个二分图，二分图由两个点集组成，每条边都连接这两个点集中的点。我们需要找到这个二分图的最大匹配，也就是最多可以有多少条边，使得每个点最多只被一条边关联。

匈牙利算法原理

匈牙利算法是解决二分图最大匹配问题的经典算法，其核心思想是寻找增广路径。增广路径是一条起始于未匹配点，结束于未匹配点，并且路径上匹配边和非匹配边交替出现的路径。通过翻转增广路径上的边（匹配边变为非匹配边，非匹配边变为匹配边），可以使匹配数增加 1。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <time.h>
#include <random>//poj*
#include <chrono>//poj*
#include <unistd.h>//poj*
#define int long long
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1000001;
using namespace std;
int n,m,e;
int h[N],vis[N],cnt,ans;
int match[N];
struct line{
    int Nxt;
    int to;
}l[N];
void Link(int u,int v){
    l[++cnt] = (line){h[u],v};
    h[u] = cnt;
}
bool findPath(int u){
    for(int i = h[u];i;i = l[i].Nxt){
        int v = l[i].to;
        if(!vis[v]){
            vis[v] = 1;
            if(!match[v] || findPath(match[v])){
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int MaxMatch(){
    int ans = 0;
    memset(match,0,sizeof(match));
    for(int u = 1;u <= n;u++){
        memset(vis,0,sizeof(vis));
        if(findPath(u)){
            ans++;
        }
    }
    return ans;
}
signed main(){
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m>>e;
    while(e--){
        int u,v;
        cin>>u>>v;
        Link(u,v);
    }
    cout<<MaxMatch()<<endl;
    return 0;
}
/*
*注释&笔记:无
*样例输入:

*样例输出:

*/

关键部分解析

1. 图的存储：

   • 使用邻接表存储二分图，line 结构体存储边的信息。

2. 核心算法：

3. 主算法流程：

   • 每次查找前重置 vis 数组，确保每次查找的独立性。

复杂度分析

• 时间复杂度： O(n \times e)，其中 n 是左部点的数量，e 是边的数量。对于每个左部点，最坏情况下需要遍历所有边。
• 空间复杂度：O(e)，主要用于存储邻接表。

注意事项

• 题目中不保证没有重边，但邻接表的存储方式自然处理了重边问题。
• 每次查找增广路径前必须重置 vis 数组，确保算法正确性。
• 匈牙利算法适用于二分图，对于一般图的最大匹配问题需要使用更复杂的算法。

感谢@whoseJam的讲解