匈牙利算法(二分图最大匹配）- hdu 过山车

Hdu 2063

• 二分图：图中的点可以分成两组U，V，所有边都是连接U,V中的顶点。等价定义是：含奇数条边的图。

• 匹配：一个匹配是一个边的集合，其中任意两条边都没有公共顶点（每个顶点只连出一条边）。随便找几条边，只要边没有公共顶点，就能构成匹配

• 最大匹配：含边数最多的匹配

• 完美匹配：一个匹配包含了图中的所有顶点。完美匹配都是最大匹配（所有点都连了边，无法再添加任何一条边，故为最大匹配）。不是每个图都存在完美匹配

• 举个栗子：考虑男女配对的问题，边表示两两之间互相有好感。完美匹配考虑的是能否让所有男孩和女孩两两配对，最大匹配考虑的是最多能让多少男女配对

• 最大匹配算法：匈牙利算法

二分图最大匹配实例

• 题意：k条边，m女孩，n男孩。接下来k行，每行描述一条边的两个顶点。问最大匹配边数。

• 思路：匈牙利算法解二分图匹配的模板题

AcCode:

#include <bits/stdc++.h>

using namespace std;

#define fre freopen("C:\\Users\\22765\\Desktop\\in.txt","r",stdin);

#define ms(a) memset((a),0,sizeof(a))

#define rep(i,a,b) for(register int (i)=(a);(i)<(b);++(i))

#define sf(x) scanf("%d",&(x))

#define reg register

typedef long long LL;

const int inf=(0x7f7f7f7f);

const int maxn=1000;

int k,m,n;

vector<int> v[maxn];

bool vis[maxn];

int part[maxn];

//find(x)：x能否找到配对的女孩

int find(int x){

	int u;

	rep(i,0,v[x].size()){//依次尝试和他有好感的每个女孩

		u=v[x][i];

		/*

		vis数组用法详解：

		如下的好感关系：

		男  女

		1   4 5

		2   5 6

		3   4 5

		0   6

		假设 1-5,2-6,3-4

		对于 0来说，先尝试6

		6没有访问过，标记为已访问

		但是6有对象了，尝试6的对象2能否找其他女孩

		2尝试找5，对于0来说，5没有访问，标记5被访问

		但是5有对象了，尝试5的对象1能都找其他女孩

		1尝试4，对于0来说，4没有访问，标记4为被访问

		但是4有对象了，尝试4的对象3能否找其他女孩

		3除了4只能找5了，但是5在第二步被标记为访问过，

		如果尝试5就会倒回第二步造成死循环。

		所以0号男孩无法找到配对的女孩，回溯一直返回false 

		*/

		if(!vis[u]){

			vis[u]=1;

			//如果女孩没有找到partner或者女孩的partner可以找其他女孩

			if(!part[u]||find(part[u])){

				part[u]=x;

				return true;

			}

		}

	}

	return false;

}

int main(){

	while(sf(k)&&k){

		scanf("%d%d",&m,&n);

		rep(i,1,n+1)v[i].clear();

		ms(part);

		int x,y;

		rep(i,0,k){

			sf(x);sf(y);

			v[y].push_back(x);//存边

		}

		int ans=0;

		rep(i,1,n+1){//对于每个男孩，找配对的女孩

			ms(vis);//每轮查找标记女孩是否访问过

			if(find(i)) ans++;

		}

		printf("%d\n",ans);

	}

	return 0;

}