题目背景
第二次界大战时期..
题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的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!’。
输入样例
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
输出样例
4
1 7
2 9
3 8
5 10
Solution
把源点都连向皇家空军，把外籍飞行员连向汇点，然后再根据题意连边。
当时这道题我其实用的是匈牙利做的
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
87
88
89
90
91
92
93
94
95
96
97
98
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAXN 1002
#define INF 2000000000
namespace STman {
template <typename Tp>
inline void read(Tp &x) {
#define C getchar()
Tp f = 1;
x = 0;
char k = C;
while (k < '0' || k > '9') {
if (k == '-') f = -1;
k = C;
}
while (k >= '0' && k <= '9') {
x = x * 10 + k - '0';
k = C;
}
x = x * f;
#undef C
}
template <typename Tp>
inline void write(Tp x) {
if (x < 0) putchar('-') , x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename Tp>
inline Tp max(Tp a , Tp b) {
if (a > b) return a;
else return b;
}
template <typename Tp>
inline Tp min(Tp a , Tp b) {
if (a < b) return a;
else return b;
}
template <typename Tp>
inline void swap(Tp &a , Tp &b) {
Tp t = a;
a = b;
b = a;
}
template <typename Tp>
inline Tp abs(Tp &a) {
if (a < 0) return -a;
else return a;
}
inline void sp() {
putchar(32);
}
inline void et() {
putchar(10);
}
}
using namespace STman;
struct Edge {
int v , nx;
}e[MAXN];
int mc[MAXN] , vis[MAXN] , n , m , ans , x , y , head[MAXN] , ecnt;
void add(int f , int t) {
e[++ecnt] = (Edge) {t , head[f]};
head[f] = ecnt;
}
bool Hungary(int k) {
for (int i = head[k] ; i ; i = e[i].nx) {
int to = e[i].v;
if (!vis[to]) {
vis[to] = 1;
if (!mc[to] || Hungary(mc[to])) {
mc[to] = k;
return 1;
}
}
}
return 0;
}
int main() {
read(m) , read(n);
read(x) , read(y);
while (x != -1 && y != -1) {
read(x) , read(y);
add(x , y);
}
for (int i = 1 ; i <= m ; i++) {
ans += Hungary(i);
memset(vis , 0 , sizeof(vis));
}
write(ans) , et();
for (int i = m + 1 ; i <= n ; i++) {
if (mc[i]) write(mc[i]) , sp() , write(i) , et();
}
return 0;
}
|
