记录编号	245602	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-04-03 20:35:37	内存使用	0.29 MiB

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <list>
#include <string>
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

#ifdef __linux__
	#define IP "flyer.in"
	#define OP "flyer.out"
#else
	#define IP "CONIN$"
	#define OP "CONOUT$"
#endif
#define MAXN (105)

ifstream IF(IP);
ofstream OF(OP);

struct edge
{
	int from, to, rem;
};

vector<int> adj[MAXN];
vector<edge> edges;
bool vis[MAXN];
int dist[MAXN];

inline void add(int from, int to)
{
	edges.push_back((edge){from, to ,1});
	edges.push_back((edge){to, from ,0});
	int c = edges.size();
	adj[from].push_back(c-2);
	adj[to].push_back(c-1);
}

int n, m;

bool bfs()
{
	memset(vis, false, sizeof(vis));
	dist[0] = 0;
	vis[0] = true;
	queue<int> q;
	q.push(0);
	
	while(q.size())
	{
		int u = q.front();
		q.pop();
		for(int i = 0; i < adj[u].size(); i++)
		{
			edge& e = edges[adj[u][i]];
			if(!vis[e.to] && e.rem > 0)
			{
				vis[e.to] = true;
				dist[e.to] = dist[u] + 1;
				q.push(e.to);
			}
		}
	}
	return vis[n+1];
}

int dfs(int cur, int flow)
{
	if(cur == n+1 || flow == 0)return flow;
	int r = 0;
	int next;
	for(int i = 0; i < adj[cur].size(); i++)
	{
		edge& e = edges[adj[cur][i]];
		if(dist[e.to] == dist[cur] + 1 && (next = dfs(e.to, min(flow, e.rem))) > 0)
		{
			e.rem -= next;
			r += next;
			flow -= next;
			edges[adj[cur][i]^1].rem += next;
			if(flow == 0)break;
		}
	}
	return r;
}

void read_data()
{
	IF >> n >> m;
	int a, b;
	while(IF >> a >> b)
	{
		add(a,b);
	}
	for(int i = 1; i <= m; i++)
		add(0, i);
	for(int i = m+1; i <= n; i++)
		add(i, n+1);
}

void solve()
{
	int f = 0;
	while(bfs())
	{
		f += dfs(0, 0x23333333);
	}
	OF << f << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	read_data();
	solve();
	return 0;
}