P2756 飞行员配对方案问题

Posted on | In

题目链接

题目背景
第二次世界大战时期..

题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的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!’。

Solution:

先在可配合的外籍飞行员与英国飞行员间连边， 流量为1， 新建超级源点， 与外籍飞行员间连边， 流量为1，
新建超级汇点， 与英国飞行员间连边， 流量为1， 然后最大流一波搞定。(此题二分图匹配也可做)

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using namespace std;

// -------------------------head start here---------------------------------------
#define pb      push_back
#define mp      make_pair
#define sz(a) (int)a.size()
#define endl    '\n'
#define all(a)  a.begin(),a.end()
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define drep(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define Rep(i, a, b) for(int i = int(a); i <= int(b); i++)
#define dRep(i, a, b) for (int i = int(a); i >= int(b); i--)
#define mst(a, x) memset(a, x, sizeof a)

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using VI = vector<int>;
using VL = vector<long long>;

const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int Move[][3] = { { 0, 0 },{ 1, 0 },{ 0, 1 },{ 0, -1 },{ -1, 0 },{ 1, 1 },{ 1, -1 },{ -1, 1 },{ -1, -1 } };

inline ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template <class T> inline ll sqr(T x) { return 1ll * x * x; }
ll qpow(ll a, int t) { a %= MOD; ll b = 1; for (; t; t >>= 1, (a *= a) %= MOD) if (t & 1) (b *= a) %= MOD; return b; }
template <class T> inline bool chkmax(T& a, T b) { return (a < b) ? (a = b, 1) : 0; }
template <class T> inline bool chkmin(T& a, T b) { return (a > b) ? (a = b, 1) : 0; }
// -----------------------------head end here-------------------------------------

struct edge {
    int v, w, next;
    edge(int vv = 0, int ww = 0, int nxt = -1) : v(vv), w(ww), next(nxt) {}
}e[MAX];

int n, m, tot;
int head[205], level[205], cur[205], link[205];

queue<int> Q;

void init() {
    tot = 0;
    memset(head, -1, sizeof head);
    memset(link, -1, sizeof link);
}

void addedge(int u, int v, int w) {
    e[tot] = edge(v, w, head[u]); head[u] = tot++;
    e[tot] = edge(u, 0, head[v]); head[v] = tot++;
}

bool bfs(int st, int ed) {
    while (!Q.empty()) Q.pop();
    memset(level, 0, sizeof level);
    Q.push(st); level[st] = 1;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; i != -1; i = e[i].next) {
            if (level[e[i].v] == 0 && e[i].w > 0) {
                level[e[i].v] = level[u] + 1;
                Q.push(e[i].v);
            }
        }
    }
    return level[ed] != 0;
}

int dfs(int u, int ed, int flow) {
    if (u == ed) return flow;
    int change = 0;
    for (int& i = cur[u]; flow > 0 && i != -1; i = e[i].next) {
        if (level[e[i].v] == level[u] + 1 && e[i].w > 0) {
            int tmp = dfs(e[i].v, ed, min(flow, e[i].w));
            if (tmp == 0) {
                continue;
            }
            link[u] = e[i].v;
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            change += tmp;
            flow -= tmp;
        }
    }
    return change;
}

int Dinic(int st, int ed) {
    int res = 0;
    while (bfs(st, ed)) {
        memcpy(cur, head, sizeof cur);
        res += dfs(st, ed, INF);
    }
    return res;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    while (cin >> m >> n) {
        init();
        int u, v;
        while (cin >> u >> v) {
            if (u == v && v == -1) break;
            addedge(u, v, 1);
        }
        for (int i = 1; i <= m; i++) {
            addedge(n + m + 1, i, 1);
        }
        for (int i = m + 1; i <= n + m; i++) {
            addedge(i, n + m + 2, 1);
        }
        int tot = Dinic(n + m + 1, n + m + 2);

        if (tot == 0) {
            cout << "No Solution!" << endl;
            continue;
        }

        cout << tot << endl;
        for (int i = 1; i <= m; i++) {
            if (link[i] != -1) {
                cout << i << " " << link[i] << endl;
            }
        }
    }
}