记录编号	348029	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2016-11-13 20:36:25	内存使用	0.44 MiB

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

const int maxnumber = 105, inf = 0x3f3f3f3f;
int n, n1, s, t;
struct Edge
{
	int to, cap, next;
}edges[maxnumber * maxnumber + 2 * maxnumber];
int head[maxnumber], tot = 1;

inline void AddEdge(const int& from, const int& to, const int& cap)
{
	edges[++tot].to = to;
	edges[tot].cap = cap;
	edges[tot].next = head[from];
	head[from] = tot;
}

struct MaxFlow
{
	bool vis[maxnumber];
	int dis[maxnumber], cur[maxnumber];
	inline bool BFS()
	{
		memset(vis, 0, sizeof vis);
		queue <int> Q;
		vis[s] = 1; dis[s] = 0;
		Q.push(s);
		while (!Q.empty()) {
			int front = Q.front(); Q.pop();
			for (int i = head[front]; i; i = edges[i].next) {
				int to = edges[i].to, cap = edges[i].cap;
				if (!vis[to] && cap) {
					dis[to] = dis[front] + 1;
					vis[to] = 1;
					Q.push(to);
				}
			}
		}
		return vis[t];
	}
	int DFS(const int& a, int minn)
	{
		if (a == t) return minn;
		int ret = 0;
		for (int& i = cur[a]; i; i = edges[i].next) {
			if (dis[edges[i].to] == dis[a] + 1 && edges[i].cap) {
				int x = DFS(edges[i].to, min(minn, edges[i].cap));
				minn -= x; ret += x;
				edges[i].cap -= x; edges[i ^ 1].cap += x;
				if (!minn) break;
			}
		}
		return ret;
	}
	inline int Work()
	{
		int ret = 0;
		while (BFS()) {
			for (int i = 1; i <= t; ++i)
				cur[i] = head[i];
			ret += DFS(s, inf);
		}
		return ret;
	}
}Dinic;

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("flyer.in", "r", stdin); freopen("flyer.out", "w", stdout);
#endif

	int from, to;
	scanf("%d%d", &n, &n1);
	s = n + 1; t = n + 2;
	while (scanf("%d%d", &from, &to) != EOF) {
		AddEdge(from, to, inf);
		AddEdge(to, from, 0);
	}
	for (int i = 1; i <= n1; ++i) {
		AddEdge(s, i, 1);
		AddEdge(i, s, 0);
	}
	for (int i = n1 + 1; i <= n; ++i) {
		AddEdge(i, t, 1);
		AddEdge(t, i, 0);
	}
	printf("%d\n", Dinic.Work());

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}