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

原创于 2024-02-27 17:40:25 发布 · 粉丝可见 · 487 阅读 · 6 · 9 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/136319468

本题链接：【模板】二分图最大匹配 - 洛谷

题目：

样例1：

`cobol<br/>1 1 1<br/>1 1<br/>`

1

样例2：

`cobol<br/>4 2 7<br/>3 1<br/>1 2<br/>3 2<br/>1 1<br/>4 2<br/>4 1<br/>1 1<br/>`

2

思路：

根据题目意思，我们由之前提及到过的二分图含义明确一下。

二分图就像是一个人群中的男女混合舞会，所有参与者可以分成两组：男生和女生。在这个舞会上，男生只和女生跳舞，而不和其他男生跳舞；女生也只和男生跳舞，而不和其他女生跳舞。没有两个男生或两个女生会成对跳舞。 只存在一对一个的关系。

换句话说，如果一个图是二分图，就意味着可以将所有的点分成两组，使得同一组内的点之间没有直接相连的边，而不同组内的点之间有直接相连的边。这种特性在很多实际问题中都有重要的应用。

这里二 分图最大匹配的可以理解为：找出尽可能多的能够一对一个结点不同染色结点的对数总量.

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
int n,m,k,ans;
 
// 数组模拟链表
vector<int>h(N,-1);
int e[N],ne[N],idx;
inline void Add(int a,int b)
{
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
 
umap<int,int>stn; // 表示 n 种类的结点是否已经匹配过
umap<int,int>stm; // 表示 m 种类的结点是否已经匹配过
 
inline bool Finds(int x)
{
	// 枚举当前结点所指向的对应 另一个种类的结点
	for(int i = h[x];i != -1;i = ne[i])
	{
		int j = e[i];	// 取出对应的结点
		if(!stm[j])	// 如果对应的结点没有匹配
		{
			stm[j] = true;	// 标记该节点可以匹配
			
			// 如果对应 m 结点没有匹配，我们将其匹配
			// 或者 匹配过了，那让 当前 m 结点匹配过了的，再另找是否有没匹配的
			if(!stn[j] || Finds(stn[j]))
			{
				stn[j] = x;
				return true;	// 返回匹配成功
			}
		}
	}
	return false;	// 如果找了一整圈下来匹配不成功，返回 false
}
 
 
inline void solve()
{
	cin >> n >> m >> k ;
	while(k--)
	{
		int a,b;
		cin >> a >> b;
		
		// 这里之所以不双向相连，
		// 是因为我们匹配查找的时候只需要遍历另一个种类的结点，找出对应的一个结点
		// 所以没必要双向连接
		Add(a,b);		
	}
	
	// 枚举 我们由 连接方式对应的种类结点,
	// 因为我们是 由 属于 n 种类的 指向 m 种类的对应结点
	// 所以我们遍历 n 个结点,属于 n 种类的
	for(int i = 1;i <= n;++i)
	{
		// 这里清除我们原先所有的匹配 m ，重新以当前的结点开始进行查找匹配
		stm.clear();	 
		if(Finds(i)) ++ans;	// 如果当前结点可以查找到匹配，那么成功数量 + 1
	}
	
	cout << ans << endl;
}
 
signed main()
{
//	freopen("a.txt", "r", stdin);
//	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}