题目大意:男女搭配,二分图模板题
思路:匈牙利算法.O(n*m)时间效率.枚举女生集合里面的每一个女生,每次都去找增广路径,
增广路径:
(1)两个点没有匹配过的,
(2)出发点和终点没有匹配过的,和已经匹配过的交替呈现 这里DFS搜就是了.
AC Program:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
typedef long long ll;
#define clr(a) memset((a),0,sizeof (a))
#define rep(i,a,b) for(int i=(a);i<(int)(b);i++)
#define per(i,a,b) for(int i=((a)-1);i>=(int)(b);i--)
#define inf 0x7ffffff
#define eps 1e-6
using namespace std;
int k,m,n;
int b[510];//boy
int g[510];//girl
int flag[510];
int mm[510][510];//map
void init(){
int vm,vn;
memset(b,-1,sizeof(b));
memset(g,-1,sizeof(g));//赋值为-1意思更贴题
memset(mm,0,sizeof(mm));
for(int i=1;i<=k;i++){
scanf("%d%d",&vm,&vn);
mm[vm][vn]=1;
}
//system("pause");
}
int findpath(int gu){
for(int i=1;i<=n;i++){
if(mm[gu][i]==1 && !flag[i]){
flag[i]=1;
if(b[i]==-1){//两个点都是未在以前的增广路径(匹配结果)中的,直接找到了增广路径
b[i]=gu; //更新匹配
g[gu]=i;
return 1;
}
else if(findpath(b[i])){//如果这个男的已经匹配过了,那么沿着他的女伴找增广路径
b[i]=gu;
g[gu]=i;
return 1;
}
}
}
return 0;
}
int XYL(){
int res=0;
for(int i=1;i<=m;i++){//m是女生的个数
if(g[i]==-1){//如果还没有在匹配的就找增广路径
memset(flag,0,sizeof(flag));
//每次进行找增广路径的时候不能走已经用过的点,有些点会回头的
//但是b[]g[]数组不改变是因为不断的寻找增广路径
//点可以已经在增广路径中,但是不能在当前要寻找的增广路径中出现2遍
res+=findpath(i);
}
}
return res;
}
int main(){
int test;
//cin>>test;
while(~scanf("%d",&k)){
if(k==0)break;
scanf("%d%d",&m,&n);
init();
printf("%d\n",XYL());
};
//system("pause");
return 0;
}