匈牙利算法(二分图最大匹配）- hdu 过山车
-
二分图：图中的点可以分成两组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
",ans);
}
return 0;
}