【COGS 14】[网络流24题] 搭配飞行员

题目传送门：http://cogs.top/cogs/problem/problem.php?pid=14
离线版题目：http://paste.ubuntu.com/18772859/

二分图匹配板题，Dinic跑一跑就ok啦！

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

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

const int MAXN = 10000+9;
const int INF = 1000000000;

int n,m,a,b,T,head[MAXN],to[MAXN],nxt[MAXN],cap[MAXN],vout;
int s,t,cur[MAXN],que[MAXN],fro,bak,dis[MAXN],flow[MAXN];

inline void AddEdge(int a, int b){
	to[++T] = b; nxt[T] = head[a]; head[a] = T; cap[T] = 1;
	to[++T] = a; nxt[T] = head[b]; head[b] = T;  
}

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	dis[s] = 0; que[fro=bak=1]=s;
	
	while (bak <= fro){
		int w = que[bak++];
		for (int i=head[w];i;i=nxt[i])
			if (flow[i] < cap[i] && dis[to[i]]==-1)
				dis[to[i]] = dis[w] + 1,
				que[++fro] = to[i];
	}
	
	if (dis[t] != -1) return true;
	else return false;
}

int MaxFlow(int w, int f){
	if (w == t) return f;
	else {
		int ret = 0;
		for (int &i=cur[w];i;i=nxt[i]){
			if (flow[i] < cap[i] && dis[to[i]] == dis[w]+1){
				int tmp = MaxFlow(to[i], min(f, cap[i]-flow[i]));
				flow[i] += tmp; flow[i^1] -= tmp;
				ret += tmp; f-=tmp;
				if (!f) return ret;
			}
		}
		return ret;
	}
}

inline void Dinic(){
	while (BFS()){
		for (int i=0;i<=n*2+1;i++)
			cur[i] = head[i];
		vout += MaxFlow(s,INF);
	}
}

int main(){
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	n = read(); m = read();
	s = 0; t = 2*n+1; T = 1;
	while (~scanf("%d%d",&a,&b)) AddEdge(a*2,b*2-1);
	for (int i=1;i<=m;i++) AddEdge(s,i*2-1);
	for (int i=m+1;i<=n;i++) AddEdge(i*2,t);
	for (int i=1;i<=n;i++) AddEdge(i*2-1,i*2);
	Dinic();
	printf("%d\n",vout);
	return 0;
}