二分图与匈牙利

-----By 蒟蒻鱼

二分图

是啥

将一个无向图的点分为两个集合且两个点集中的点在各自集合中互不相连则称这个图为二分图.

性质

一个无向图是二分图,当且仅当它不包含奇环

一个无向图是二分图,当且仅当它可以二染色

判定

无向图K为二分图的充分必要条件是

1.K至少包含两个点

2.其回路的长度均为偶数

实现代码

二染色判定二分图


bool paint(now, mark)
{ 
	if (color[now] == 0) 
		color[now] = mark; 
	else if (color[now] != mark) 
		return false;
	int k=head[now]; 
	while (k!=0){ 
		if(paint(e[k], -mark)==false) 
		return false; k=next[k];   //如出现冲突则说明这不是
	} 
	return true; //没有出现冲突说明此图是二分图
}

二分图的匹配

是啥

对于一个二分图K的子图T

若T的边集E的任意两条边都不连接同一个点,则称T为K的一个匹配

关于二分图的最大匹配

匈牙利算法

首先了解一个定义:增广路

定义:
设M是二分图G的一个匹配,P是G中一个连通两个未匹配点的路径,且属于M的边与不属于M的边交替出现，则称P为相对于M的一条增广路.

由增广路的定义可以推出下述三个结论

1.增广路的路径长度必定为奇数,第一条边和最后一条边都未被匹配.

2.通过增广路的交错可以得到一个更大的匹配.

3.当且仅当不存在增广路是匹配数最大.

如何找？(染色法)

1.设增广路M为空

2.找出一条增广路P通过取反操作获得更大的匹配代替原匹配M

3.重复2.的操作直到找不出新的增广路为止

如何进行2.的操作？

~~好像就只有这个问题比较棘手~~

枚举一条路径的起始点

判断此点是否为初始状态

dfs将下一个点赋为 !这个点的颜色

最后一直找到找不到增广路便返回

开始打增广路部分


bool ap(int x){
	for(int i=1;i<=m;i++){//扫描每一个点 
		if(g[x][i]&&!vis[i])//如果x,i之间存在一条边且i未被访问过
		vis[i]=true; //将i点标记为过
		if(!match[i]||ap(match[i])){ //如果这是增广路的中点或还能从这个点找到增广路 
			match[i]=x;  
			return true;//能找到 
		} 
	}
	return false; //如果扫描了每一个点都无法找到增广路就说明找不到增广路了 
}

完整代码:


#include<bits/stdc++.h>
using namespace std;
int ans=0;
const int maxn=1007;
bool vis[maxn];
int n,m;
int e;
bool g[maxn][maxn];
int match[maxn];
bool ap(int x){
	for(int j=1;j<=m;++j){//扫描每一个点 
		if(g[x][j]&&!vis[j]){//如果x,j之间存在一条边且j未被访问过
			vis[j]=true; //将j点标记为过
			if(!match[j]||ap(match[j])){ //如果这是增广路的中点或还能从这个点找到增广路 
				match[j]=x;  //变反 
				return true;//返回能找到 
			} 
		} 
	}
	return false; //如果扫描了每一个点都无法找到增广路就说明找不到增广路了 
}
void work()
{
	for(int i=1;i<=n;++i){ //枚举增广路起始点
		memset(vis,0,sizeof(vis));
		if(ap(i)){
			ans++;
		} 
	}
	return ;
}
int main()
{
	cin>>n>>m>>e;
	for(int i=1;i<=e;i++){
		int u,v;
		cin>>u>>v;
		g[u][v]=true; 
	}
	work();
	cout<<ans;
}

颓了