记录编号	355916	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-11-28 20:43:33	内存使用	0.32 MiB

/*

14

flyer.in

*/


#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>


using namespace std;
const int nmax=186;
const int INF=1<<29;


int n,m;
int u,v;
int s,t;

bool vis[nmax]={0};
int d[nmax]={0};


class edge
{
public:
	int from,to;
	int flow,cap;
};


vector<edge> edges;
vector<int > G[nmax]; 


void AddEdge(int from,int to,int cap)
{
	edges.push_back((edge){from,to,0,cap});
	G[from].push_back(edges.size()-1);
	edges.push_back((edge){to,from,0,0});
	G[to].push_back(edges.size()-1);
}


void PreDo()
{
	scanf("%d%d",&n,&m);
	s=0;
	t=n+1;
	for(int i=1;i<=m;i++)
	{
		AddEdge(s,i,1);
	}
	while(scanf("%d%d",&u,&v)==2)
	{
		AddEdge(u,v,1);
	}
	for(int i=m+1;i<=n;i++)
	{
		AddEdge(i,t,1);
	}

}


bool BFS()
{
	memset(vis,0,sizeof(vis));
	queue<int > Q;
	Q.push(s);
	vis[s]=1;
	d[s]=0;
	while(!Q.empty())
	{
		int tmpx=Q.front();
		Q.pop();
		for(int i=0;i<G[tmpx].size();i++)
		{
			edge &e=edges[G[tmpx][i]];
			if(e.cap<=e.flow||vis[e.to])
			{
				continue;
			}
			vis[e.to]=1;
			d[e.to]=d[tmpx]+1;
			Q.push(e.to);
		}
	}
	return vis[t];
}


int DFS(int tmpx,int a)
{
	if(a==0||tmpx==t)
	{
		return a;
	}
	int flow=0;
	int f=0;
	for(int i=0;i<G[tmpx].size();i++)
	{
		edge &e=edges[G[tmpx][i]];
		if(d[tmpx]+1==d[e.to])
		{
			f=DFS(e.to,min(a,e.cap-e.flow));
			if(f>0)
			{
				e.flow+=f;
				edges[G[tmpx][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(a<=0)
				{
					break;
				}
			}
		}
	}
	return flow;
}


int Dinic(int s,int t)
{
	int ans=0;
	while(BFS())
	{
//		printf("%d\n",BFS());
		ans+=DFS(s,INF);
	}
	printf("%d\n",ans);
}

	
int main()
{
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	PreDo();
	Dinic(s,t);
	return 0;
}