# Bzoj1191 [hnoi2006]超级英雄hero

Posted by yjjr's blog on February 6, 2018

Description

Input

Output

Sample Input

5 6
3 2
2 0
0 3
0 4
3 2
3 2

Sample Output

4

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
{
ll f=1,x=0;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;
}
const int maxn=1506;
int match[maxn][maxn],use[maxn],result[maxn],n,m,ans=0;
bool dfs(int now)
{
rep(i,0,n-1)
if(match[now][i]&&!use[i]){
use[i]=true;
if(!result[i]||dfs(result[i])){
result[i]=now;
return true;
}
}
return false;
}
int main()
{
rep(i,1,m){
match[i][x]=match[i][y]=1;
}
rep(i,1,m){
mem(use,0);
if(dfs(i))ans++;else break;
}
cout<<ans<<endl;
return 0;
}