代码 · DTOJ.飞行员配对方案

#include <bits/stdc++.h>
#include <queue>
#define il inline
using namespace std;

int n, m, T[105][105], Pre[105], Flow[105], Max;
queue<int> Q;

il int BFS(){
	while(!Q.empty()) Q.pop();
	memset(Pre, -1, sizeof Pre);
	Pre[0] = 0;
	Q.push(0);
	while(!Q.empty()){
		int k = Q.front(); Q.pop();
		if(k == n) break;
		for(int i=1; i<=n; ++i)
			if(T[k][i] && Pre[i]==-1){
				Pre[i] = k;
				Flow[i] = min(Flow[k], T[k][i]);
				Q.push(i); 
			}
	}
	return Pre[n]==-1?-1:Flow[n];
}
il void PreWork(){
	for(int i=1; i<=m; ++i) T[0][i] = 1;
	for(int i=m+1; i<=n; ++i) T[i][n+1] = 1;
	Flow[0] = 1e9;
	++n;
}
il void EK(){
	int incs;
	while(incs=BFS() != -1){
		int k = n;
		while(k != 0){
			int lst = Pre[k];
			T[lst][k] -= incs, 
			T[k][lst] += incs,
			k = lst;
		}
		Max += incs;
	}
}
int main(){
	int a, b;
	scanf("%d%d", &m, &n);
	while(scanf("%d%d", &a, &b) && a!=-1) T[a][b] = 1;
	PreWork();
	EK();
	if(!Max) puts("No Solution!");
	else printf("%d", Max);
	return 0;
	
}