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

二分图最大匹配问题题解

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

问题分析

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

匈牙利算法原理

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

1

。

AC代码

CPP

#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;
}
/*
*注释&笔记:无
*样例输入:

*样例输出:

*/

关键部分解析

图的存储：
- 使用邻接表存储二分图， $line$ 结构体存储边的信息。
- $Link$ 函数用于添加边，采用头插法构建邻接表。
核心算法：
- $findPath$ 函数用于寻找增广路径，使用 DFS 实现。
- $vis$ 数组标记右部点是否在当前查找中已被访问。
- $match$ 数组记录右部点的匹配情况。
主算法流程：
- $MaxMatch$ 函数遍历左部所有点，尝试为每个点寻找匹配。
- 每次查找前重置 $vis$ 数组，确保每次查找的独立性。

复杂度分析

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

注意事项

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

感谢@whoseJam的讲解

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

文章操作

二分图最大匹配问题题解

问题分析

匈牙利算法原理

AC代码

关键部分解析

复杂度分析

注意事项

相关推荐

评论

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