现在的位置: 首页 > 算法 > 正文

[Bzoj1191][HNOI2006]超级英雄Hero

2018年01月13日 算法 ⁄ 共 586字 ⁄ 字号 评论关闭
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,ans,lk[1001];
bool f[1001][1001],vis[1001];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool find(int x){
	for(int i=0;i<=n-1;i++){
		if(!vis[i]&&f[x][i]){
			vis[i]=1;
			if(!lk[i]||find(lk[i])){
				lk[i]=x;return 1;
			}
		}
	}
	return 0;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int a=read(),b=read();
		f[i][a]=f[i][b]=1;
	}
	for(int i=1;i<=m;i++){
		memset(vis,0,sizeof(vis));
		if(find(i))ans++;
		else break;
	}
	printf("%d",ans);
	return 0;
} 

抱歉!评论已关闭.