记录编号	148410	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	vampire	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-02-11 21:09:35	内存使用	3.20 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int level[110]={0},gap[110]={0},pre[110],map[110][110]={0},n,m;
int ISAP(int x,int y){
	int u,v,minn,ans=0,maxn,i;
	memset(pre,-1,sizeof(pre));
	pre[x]=x;u=x;gap[0]=n;
	while(level[x]<n){
		for(v=1;v<=n;++v){
			if(map[u][v]>0&&level[v]+1==level[u]){
				break;
			}
		}
		if(v<=n){
			pre[v]=u;u=v;
			if(v==n){
				maxn=100000000;
				for(i=v;i!=x;i=pre[i]){
					maxn=min(maxn,map[pre[i]][i]);
				}
				ans+=maxn;
				for(i=v;i!=x;i=pre[i]){
					map[pre[i]][i]-=maxn;
					map[i][pre[i]]+=maxn;
				}
				u=x;
			}
		}
		else{
			minn=n;
			for(v=1;v<=n;++v){
				if(map[u][v]>0){
					minn=min(minn,level[v]);
				}
			}
			minn+=1;
			gap[level[u]]-=1;
			if(!gap[level[u]]) break;
			level[u]=minn;
			gap[level[u]]+=1;
			u=pre[u];
		}
	}
	return ans;
}
int main()
{
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	int i,j,x,y;
	scanf("%d%d",&n,&m);
	while(scanf("%d%d",&x,&y)==2){
		map[1][x+1]=1;
		map[y+1][n+2]=1;
		map[x+1][y+1]=1;
	}
	n+=2;
	printf("%d\n",ISAP(1,n));
}