记录编号	390118	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-04-01 21:20:52	内存使用	0.00 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define is_num(tmp) (tmp<='9' and tmp>='0')
#define MAXN 110
#define INF 0x7fffffff

const inline int in(void){
	char tmp = getchar();
	int res = 0;
	while(!is_num(tmp))tmp = getchar();
	while(is_num(tmp))
		res = (res<<1) + (res<<3) + (tmp^48),
		tmp = getchar();
	return res;
}

class FLOW{
private:
	struct EDGE{
		int fr, to;
		int v, ne;
		
		EDGE(){;}
		EDGE(const int& _fr, const int& _to, const int& _v, const int& _ne){
			fr = _fr, to = _to, v = _v, ne = _ne;
		}
	};
	EDGE edge[MAXN*MAXN*2];
	int head[MAXN], tot;
	const inline void add_edge(const int& fr, const int& to, const int& v){
		edge[++tot] = EDGE(fr, to, v, head[fr]), head[fr] = tot;
		return ;
	}
	
	int N, n1, S, T;
	int Max_flow;
	bool exist[MAXN];
	int pre[MAXN];
	queue<int>que;
	
	const inline void get_map(void){
		N = in(), n1 = in();
		int a, b;
		while(scanf("%d %d", &a, &b) != EOF){
			add_edge(a, b, INF);
			add_edge(b, a, 0);
		}
		
		S = 0, T = N + 1;
		
		for(int i = 1; i <= n1; ++i){
			add_edge(S, i, 1);
			add_edge(i, S, 0);
		}
		
		for(int i = n1+1; i <= N; ++i){
			add_edge(i, T, 1);
			add_edge(T, i, 0);
		}
		
		return ;
	}
	
	const inline bool bfs(void){
		memset(exist, 0, sizeof(exist));
		memset(pre, 0, sizeof(pre));
		while(!que.empty())que.pop();
		
		que.push(S);
		exist[S] = true;
		
		int now, to;
		while(!que.empty()){
			now = que.front();
			que.pop();
			if(now == T)return true;
			
			for(int i = head[now]; i; i = edge[i].ne){
				to = edge[i].to;
				if(exist[to] || edge[i].v <= 0)continue;
				
				que.push(to);
				exist[to] = true;
				pre[to] = i;
			}
		}
		
		return exist[T];
	}
	
	const inline bool get_flow(void){
		int min_flow = INF;
		int now = pre[T];
		
		while(now){
			min_flow = min(min_flow, edge[now].v);
			now = pre[edge[now].fr];
		}
		
		now = pre[T];
		
		while(now){
			edge[now].v -= min_flow;
			if(now & 1)edge[now+1].v += min_flow;
			else edge[now-1].v += min_flow;
			now = pre[edge[now].fr];
		}
		
		return min_flow;
	}
public:
	
	int work(void){
		Max_flow = 0;
		get_map();
		while(bfs()){
			Max_flow += get_flow();
		}
		
		return Max_flow;
	}
};

FLOW a;

void *Main(){
#ifndef LOCAL
	freopen("flyer.in", "r", stdin);
	freopen("flyer.out", "w", stdout);
#endif
	printf("%d", a.work());
	
	return NULL;
}
void *Main_(Main());
int main(){;}