[网络流24题]飞行员配对方案问题

Posted on | In , , , ,
网络流24题·1

题目

背景

第二次世界大战时期..

描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的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
2
3
4
5
6
7
8
9
10
11
12
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
2
3
4
5
4
1 7
2 9
3 8
5 10

解题思路

裸的二分图匹配问题
用网络流做重在构图：源点 S 向 1~m 连容量为 1 的边，m+1~n 向汇点 T 连容量为 1 的边，能匹配的也连容量为 1 的边。这样，最大匹配即是最大流。

下面是 Dinic 算法跑最大流的代码。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

const int INF = 1e9;
const int N = 205;

int n, m, u, v, S, T;

struct Edge{
	int from, nxt, to, cap;
}edge[N*N*2];
int head[N], edgeNum = 1;
void addEdge(int from, int to, int cap){
	edge[++edgeNum].nxt = head[from];
	edge[edgeNum].from = from;
	edge[edgeNum].to = to;
	edge[edgeNum].cap = cap;
	head[from] = edgeNum;
}

int lay[N];
bool bfs(){
	memset(lay, 0, sizeof lay);
	queue<int> q;
	q.push(S);
	lay[S] = 1;
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(int i = head[cur]; i; i = edge[i].nxt){
			if(edge[i].cap <= 0)	continue;
			if(!lay[edge[i].to]){
				lay[edge[i].to] = lay[cur] + 1;
				q.push(edge[i].to);
			}
		}
	}
	return lay[T];
}
int dfs(int x, int minn){
	if(x == T)	return minn;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].cap <= 0 || lay[edge[i].to] != lay[x] + 1)	continue;
		int t = dfs(edge[i].to, min(minn, edge[i].cap));
		if(t){
			edge[i].cap -= t;
			edge[i^1].cap += t;
			return t;
		}
	}
	return 0;
}
int dinic(){
	int maxFlow = 0;
	while(bfs())
		if(int flow = dfs(S, INF))
			maxFlow += flow;
	return maxFlow;
}

int main(){
	scanf("%d%d", &m, &n);
	S = n + 1, T = n + 2;
	for(int i = 1; i <= m; i++){
		addEdge(S, i, 1);
		addEdge(i, S, 0);
	}
	for(int i = m + 1; i <= n; i++){
		addEdge(i, T, 1);
		addEdge(T, i, 0);
	}
	while(scanf("%d%d", &u, &v) && (u != -1 && v != -1)){
		addEdge(u, v, 1);
		addEdge(v, u, 0);
	}
	int ans = dinic();
	if(ans == 0)	return puts("No Solution!"), 0;
	printf("%d\n", ans);
	for(int i = 1; i <= edgeNum; i += 2)
		if(edge[i].cap == 1 && edge[i].from != S && edge[i].from != T && edge[i].to != S && edge[i].to != T)
			printf("%d %d\n", edge[i].from, edge[i].to);
	return 0;
}