题目描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入格式

第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数(m<=n)。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。

接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。最后以 2个-1 结束。

输出格式

第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

输入输出样例

输入 #1
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

输出 #1

4
1 7
2 9
3 8
5 10

分析

这题是二分图的最大匹配问题，可以用网络流解决。
解决方法是，对每一个匹配连一条容量为 1 1 1 的边，建一个超级源点和超级汇点，将源点向二分图左边每个点连一条容量为 1 1 1 的边，将二分图右边每个点向汇点连一条容量为 1 1 1 的边，如图。

从 s s s 到 t t t 跑最大流，就可以得到最大匹配数了。一个流对应一个匹配。
我用的是dinic 来求最大流。

代码如下

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 100005
#define inf 2147483647
using namespace std;
struct node{
	int a, b, c, n;
}d[N * 4];
int tot, s, t;
int cnt = 1, h[N], dep[N], cur[N], ans;
void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
int bfs(){
	int i, a, b, c;
	queue<int> q;
	memset(dep, 0, sizeof(dep));
	for(i = 1; i <= tot; i++) cur[i] = h[i];
	q.push(s);
	dep[s] = 1;
	while(!q.empty()){
		a = q.front();
		q.pop();
		for(i = h[a]; i; i = d[i].n){
			b = d[i].b;
			c = d[i].c;
			if(!dep[b] && c > 0){
				dep[b] = dep[a] + 1;
				q.push(b);
			}
		}
	}
	if(dep[t] > 0) return 1;
	return 0;
}
int dfs(int a, int flow){
	int i, b, w, c, used = 0;
	if(a == t){
		ans += flow;
		return flow;
	}
	for(i = cur[a]; i; i = d[i].n){
		cur[a] = i;
		b = d[i].b;
		c = d[i].c;
		if(dep[b] == dep[a] + 1 && c){
			if(w = dfs(b, min(c, flow - used))){
				d[i].c -= w;
				d[i ^ 1].c += w;
				used += w;
			}
			if(used == flow) break;
		}
	}
	return used;
}
int main(){
	int i, j, k, n, m, a, b;
	while(scanf("%d%d", &n, &m) != EOF){
		memset(h, 0, sizeof(h));
		memset(dep, 0, sizeof(dep));
		cnt = 1;
		tot = n + m + 2;
		ans = 0;
		s = n + m + 1, t = n + m + 2;
		for(i = 1; i <= n; i++){
			scanf("%d", &k);
			for(j = 1; j <= k; j++){
				scanf("%d", &b);
				b += n;
				cr(i, b, 1);
				cr(b, i, 0);
			}
		}
		for(i = 1; i <= n; i++){
			cr(s, i, 1);
			cr(i, s, 0);
		}
		for(i = n + 1; i <= n + m; i++){
			cr(i, t, 1);
			cr(t, i, 0);
		}
		while(bfs()){
			while(dfs(s, inf));
		}
		printf("%d\n", ans);
	}
	return 0;
}