记录编号	149138	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-02-19 18:53:56	内存使用	0.54 MiB

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <queue>
using namespace std;
#ifdef DEBUG
FILE *in = fopen("test.txt", "r");
#define out stdout
#else
FILE *in = fopen("flyer.in", "r");
FILE *out = fopen("flyer.out", "w");
#endif
#define getc() fgetc(in)
template<class T>inline bool getd(T &x){
	int ch = getc();bool neg = false;
	while(ch != EOF && ch != '-' && !isdigit(ch))ch = getc();
	if(ch == EOF)return false;
	if(ch == '-')neg = true, ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
	return true;
}
/******************************************************************/
const int maxn = 250, maxe = 20002;
struct Edge{
	int u, v, c;
	inline void set(int fr, int to, int vol){u = fr, v = to, c = vol;}
}E[maxe], *Eend = E, *from[maxn];

int A, B, S, T, Ans, h[maxn];

vector<Edge*> adj[maxn];

inline void AddE(int u, int v, int vol){
	Eend->set(u, v, vol);++Eend;
	Eend->set(v, u, 0);++Eend;
}

inline void init(){
	bool used[maxn];
	getd(B), getd(A);
	T = B + 1;B -= A;
	int a, b, c, d;
	while(getd(a), getd(b))used[a] = used[b] = true, AddE(a + T, b, 1);
	for(int i = 1;i <= A;++i)if(used[i])AddE(0, i, 1), AddE(i, i + T, 1);
	for(int i = A + 1;i < T;++i)if(used[i])AddE(i + T, T, 1), AddE(i, i + T, 1);
	Edge *it;
	for(it = E;it < Eend;it += 2)adj[it->u].push_back(it);
	for(it = E + 1;it < Eend;it += 2)adj[it->u].push_back(it);
}

inline bool BFS(){
	bool vis[maxn] = {1};
	queue<int> Q;Q.push(0);
	vector<Edge*>::iterator it;
	int cur;
	while(!Q.empty()){
		cur = Q.front();Q.pop();
		for(it = adj[cur].begin();it != adj[cur].end();++it)if((*it)->c && !vis[(*it)->v]){
			vis[(*it)->v] = true;
			h[(*it)->v] = h[cur] + 1;
			Q.push((*it)->v);
		}
	}
	return vis[T];
}

bool vis[maxn] = {1};
void DFS(int cur){
	if(vis[T])return;
	vector<Edge*>::iterator it;
	for(it = adj[cur].begin();it != adj[cur].end();++it)if((*it)->c&&!vis[(*it)->v]&&h[(*it)->v]-h[cur]==1){
		vis[(*it)->v] = true;
		from[(*it)->v] = *it;
		DFS((*it)->v);
	}
}

#define ops(e) (E + ((e - E) ^ 1))

inline void Aug(){
	++Ans;
	for(Edge *it = from[T];;it = from[it->u]){
		--it->c;
		++(ops(it)->c);
		if(it->u == S)break;
	}
}

inline void work(){
	bool cont;
	while(BFS()){
		cont = true;
		while(cont){//仍然存在可行流
			memset(vis + 1, 0, sizeof(bool) * (T * 2 + 1));
			DFS(0);
			if(!vis[T]){
				cont = false;
				break;
			}
			Aug();
		}
	}
	fprintf(out, "%d\n", Ans);
}

int main(){
	init();
	work();
	#ifdef DEBUG
	printf("\n%.2lfsec\n", (double)clock() / CLOCKS_PER_SEC);
	#endif
	return 0;
}