BZOJ 1191: [HNOI2006]超级英雄Hero

starli posted @ 2016年2月08日 17:00 in 二分图 , 447 阅读

二分图匹配 从第一个开始找匹配 找到第一个无法匹配的break并输出

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1010;
int help[N][2],from[N],n,m,ans,flag[N];
bool hungary(int x){
	for(int i=0;i<=1;i++) {
		int tmp=help[x][i];
		if(flag[tmp]) continue;else flag[tmp]=1;
		if(!from[tmp] || hungary(from[tmp])){from[tmp]=x;return true;}
	}
	return false;
}
int main(){
	//freopen("1191.in","r",stdin);freopen("1191.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&help[i][0],&help[i][1]);
	for(int i=1;i<=m;i++){
		memset(flag,0,sizeof(flag));
		if(hungary(i)) ans++;else break;
	}
	printf("%d",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter