【Note】二分图最大匹配 - boy and girl（P3386 题解）

本文介绍匈牙利算法，博客食用更佳。

引入

一个无向图

G

，

G

中所有点可以被分为两个点集

A

和

B

。

G

中任意边均满足：该边所连两点分别属于

A

和

B

。这样的图就叫二分图。

二分图最大匹配问题就是：选出一个边集

M

，使任意一点所连的边中只有一条属于

M

，问

M

中最多可以有多少边？

很难看对吧，换个大家喜闻乐见的方式

~~（这里是非诚勿扰）接下来有请男嘉宾登场！~~

目前有

n

个男孩和

m

个女孩，其中只能男女配对，男孩女孩间互有好感。

目前你已经知道那些男孩和女孩互有好感，你的任务是配对出尽量多的搭档。（对！仅仅是搭档！）

算法介绍

具体的，若男孩

u

和女孩

v

互有好感，就建一条连接

u

和

v

的边。于是，我们就能拿到一张~~关系表~~二分图。接下来枚举每个男孩（强制

n \le m

，可以优化常数），让男孩（设他编号为

i

）进入找搭档流程（即在二分图上跑如下流程的 DFS）：

枚举和这个男孩互有好感的女孩。
如果该女孩还没被配对，那就组合成功。
如果该女孩已经被配对了，那就把她之前的搭档拆掉（惊）！让之前和她搭档的男孩（不妨设他编号为 $j$ $j$ ）重新找一个搭档（即男孩 $j$ 进入找搭档流程）。
- 如果男孩 $j$ 找到了新搭档，就把男孩 $i$ 和当前枚举的女孩配对。
- 如果男孩 $j$ 没找到新搭档，就让男孩 $i$ 考虑下一个和他互有好感的女孩。
如果男孩 $i$ 枚举完所有和他互有好感的女孩后都没戏，那他就只能和中国剩余定理（中国单身狗定理）殊途同归，成功落单了。

正确性及时间复杂度证明

Berge 定理

我们在二分图上找一条路径，若路径由选中的边（即该边所连的男孩和女孩决定配对）和没选中的边交替组成，且第一条边和最后一条边均未被选，我们称该路径为增广路径。容易发现，我们把任意增广路上的边的被选状态反转（即之前没选的选上，之前选了的又不选了），方案依然合法，且被选中的边数还比之前多一条（即多了一对搭档）。

由此可知，存在增广路径就代表还有更优方案，最终我们就得到了 Berge 定理：一个匹配是最大匹配当且仅当图中不存在增广路径。

而匈牙利算法为每个男孩尝试寻找增广路径：若找到，匹配数增加。若找不到，当前匹配数已最大化。综上，可证匈牙利算法的正确性。

设

n

为左侧节点数（男孩数，较小侧），

m

为右侧节点数（女孩数），

E

为总边数。

单次 DFS 的复杂度：DFS 遍历

u

的所有出边（即好感女孩），并通过维护一个布尔型数组确保每个女孩在单次 DFS 中仅被访问一次，每条边最多被访问一次（当检查女孩

v

时）。最坏情况下，单次的 DFS 时间复杂度为

O(E)

（需遍历所有边）。

遍历所有

n

个男孩，对每个男孩跑 DFS，执行

n

次。每次 DFS 最坏为

O(E)

。所以，总时间复杂度为

O(nE)

。

代码实现

注释里已经讲的很清楚了，自己看代码吧。

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,E,mat[1003],ans;
//mat[i]:和编号为i的girl配对的boy的编号
bool vis[1003],F;
//vis:编号为i的girl在这一轮有(true)没有(false)找过boyfriend
vector<int> e[502];//存边:only boy->girl
//将题意转化为:
//有n个男孩,m个女孩和E个边
//若1个男孩和1个女孩互有好感,可以配对,则称为有1个边
//问最多能组成多少对lovers(a boy and a girl)

//编号为i的男孩找girlfriend,找到返回true,没找到返回false
bool f(int u){
	for(int v:e[u]) if(!vis[v]){
//		枚举和编号为u的男孩互有好感且本轮还没找过boyfriend的女孩
		vis[v]=true;//编号为i的girl找过boyfriend了
		if(mat[v]==0||f(mat[v])){//可否配对
			mat[v]=u;
			return true;
		}
	}
	return false;
}

int main(){
	scanf("%d%d%d",&n,&m,&E);
	if(n>m) swap(n,m),F=true;//强制定义人少的那一方是男孩
	for(int i=1,u,v;i<=E;i++){
		scanf("%d%d",&u,&v);
		if(F) swap(v,u);
//		如故男孩是因为强制转换变为人少的那一方,那这里也要转换
		e[u].push_back(v+n);
//		防止boy和girl编号重复,给girl的编号加上n
	}
	for(int i=1;i<=n;i++){//枚举每一个男孩
		memset(vis,0,sizeof(vis));
		if(f(i)) ans++;//若编号为i的男孩配对成功了,那么ans加1
	}
	printf("%d",ans);
	return 0;
}

【Note】二分图最大匹配 - boy and girl（P3386 题解）

文章操作

引入

很难看对吧，换个大家喜闻乐见的方式

算法介绍

正确性及时间复杂度证明

Berge 定理

代码实现

相关推荐

评论

【Note】二分图最大匹配 - boy and girl（P3386 题解）