记录编号	144556	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-12-24 07:02:35	内存使用	0.49 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int QWQ=1e8;
int n,n1,i,j,p,zj1,zj2,zj3,zj4,ans=0,ST,SD,sj=1,sj2=0,UU,VV;
int to[20100]={0},ne[20100]={0},w[20100]={0},head[110]={0};
int	zhi[110]={0},D[110]={0};
int QUEUE[110]={0},QUEUE_HEAD=1,QUEUE_TAIL=0;
bool flag[110]={0};
int GET()
{
	int x=QUEUE[QUEUE_HEAD];
	flag[x]=0;
	QUEUE_HEAD++;QUEUE[0]--;
	if(QUEUE_HEAD>105)QUEUE_HEAD=1;
	return x;
}
void PUSH(int x)
{
	QUEUE_TAIL++;QUEUE[0]++;
	if(QUEUE_TAIL>105)QUEUE_TAIL=1;
	QUEUE[QUEUE_TAIL]=x;
	flag[x]=1;
}//队列实现
void ADD(int u,int v)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj;w[sj]=1;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj;w[sj]=0;
}
void init()
{
	scanf("%d%d",&n,&n1);
	ST=n+1,SD=n+2;
	while(scanf("%d%d",&zj1,&zj2)!=EOF)
	{
		flag[zj1]=1;
		ADD(zj1,zj2);
	}
	for(i=1;i<=n;i++)
	{
		if(flag[i])ADD(ST,i),flag[i]=0;
		else ADD(i,SD);
	}
}
void flowpush(int x)
{
	while(zhi[x])
	{
		zj2=D[x]-1;zj4=QWQ;
		for(i=head[x];i;i=ne[i])
		if(w[i]>0)
		{
        	if(D[to[i]]==zj2)
        	{
				zj3=min(zhi[x],w[i]);
				zhi[to[i]]+=zj3,zhi[x]-=zj3,w[i]-=zj3,w[i^1]+=zj3;
				if(to[i]!=UU&&to[i]!=VV&&zhi[to[i]])PUSH(to[i]);
				if(!zhi[x])return;
			}
			else if(D[to[i]]<zj4)zj4=D[to[i]];
		}
		D[x]=zj4+1;
	}
}
void flow(int U,int V)
{
	UU=U,VV=V;
	for(i=1;i<=n;i++)zhi[i]=D[i]=0;
	zhi[U]=QWQ,zhi[V]=0,D[U]=V;
	for(i=head[U];i;i=ne[i])
	if(w[i]>0)
	{
		zhi[to[i]]+=w[i];w[i^1]+=w[i],w[i]=0;
		if(to[i]!=V)PUSH(to[i]);
	}
	while(QUEUE[0])
	{
		zj1=GET();
		flowpush(zj1);
	}
}
int main()
{
    //freopen("a.txt","r",stdin);
    freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	init();
	flow(ST,SD);
	ans=zhi[SD];
	printf("%d\n",ans);
	//while(1);
	return 0;
}