匈牙利算法

作用

寻找二分图最大匹配值

参考博客

趣写算法系列之–匈牙利算法

代码实现

存储结构

const int maxn=1105;
bool mp[maxn][maxn];//邻接矩阵存图
bool vis[maxn];	//标记数组
int mark[maxn];//匹配的两个点

所需函数

dfs递归找增广路

bool dfs(int x){
	for(int i=0;i<n;i++){
		if(mp[x][i]&&!vis[i]){//一次递归中数据仅可被更改一次
			vis[i]=true;
		 	if(mark[i]==-1||dfs(mark[i])){//找一个没被匹配过的，并更改值
				mark[i]=x;
				return true;
			}	
		}
	}
	return false;
}

main函数

初始化

int cnt=0;
memset(mark,-1,sizeof(mark));
memset(mp,false,sizeof(mp));

邻接矩阵存图

for(int i=0;i<n;i++){
			scanf("%d: (%d)",&u,&m);
			while(m--){
				scanf("%d",&v);
				mp[u][v]=true;
			}
		}

遍历

	//遍历确定是否存在增广路
	for(int x=0;x<n;x++){
					memset(vis,false,sizeof(vis));
					if(dfs(x)) cnt++;
				}

例题

1.HDU - 1068 Girls and Boys

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1105;
bool mp[maxn][maxn];
int n;
bool vis[maxn];
int mark[maxn];
bool dfs(int x){
	for(int i=0;i<n;i++){
		if(mp[x][i]&&!vis[i]){
			vis[i]=true;
		 	if(mark[i]==-1||dfs(mark[i])){
				mark[i]=x;
				return true;
			}	
		}
	}
	return false;
}
int main(){
	while(~scanf("%d",&n)){
		int m;
		int u,v;
		int cnt=0;
		memset(mark,-1,sizeof(mark));
		memset(mp,false,sizeof(mp));
		for(int i=0;i<n;i++){
			scanf("%d: (%d)",&u,&m);
			while(m--){
				scanf("%d",&v);
				mp[u][v]=true;
				
			}
		}
		for(int x=0;x<n;x++){
					memset(vis,false,sizeof(vis));
					if(dfs(x)) cnt++;
				}
				//printf("%d\n",cnt);
		printf("%d\n",n-cnt/2);
	}
	return 0;
}

2.HDU - 1498 50 years, 50 colors

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int mmp[maxn][maxn];
bool mp[maxn][maxn];
int n,m;
int book[maxn];
bool vis[maxn];
int mark[maxn];
bool dfs(int x){
	for(int i=1;i<=n;i++){
		if(mp[x][i]&&!vis[i]){
			vis[i]=true;
		 	if(!mark[i]||dfs(mark[i])){
				mark[i]=x;
				return true;
			}	
		}
	}
	return false;
}
int main(){
	while(scanf("%d%d",&n,&m),n||m){
		int k=1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				scanf("%d",&mmp[i][j]);
			}
		//对于每一个气球颜色去遍历二维数组 
		for(int i=1;i<=50;i++){
			int cnt=0; 
			memset(mark,0,sizeof(mark));
			//标记数组中的该颜色 
			for(int x=1;x<=n;x++)
				for(int y=1;y<=n;y++){
					if(mmp[x][y]==i)
						mp[x][y]=true;
					else
						mp[x][y]=false;
				}
			//把该颜色求最大匹配 
			for(int x=1;x<=n;x++){
					memset(vis,false,sizeof(vis));
					if(dfs(x)) cnt++;
				}
			//大于m，记为不能砸碎的颜色
				if(cnt>m) book[k++]=i;
			}
			if(k==1) printf("-1\n");
			else{
				printf("%d",book[1]);
				for(int i=2;i<k;i++)
				printf(" %d",book[i]);
				printf("\n");
			}
		}	
	return 0;
}