「网络流 24 题」飞行员配对方案 - 最大流

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷连接

一共有 \(n\) 个飞行员，其中有 \(m\) 个外籍飞行员和 \((n - m)\) 个英国飞行员，外籍飞行员从 \(1\) 到 \(m\) 编号，英国飞行员从 \(m + 1\) 到 \(n\) 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于 \(100\%\) 的数据，保证 \(1 \leq m \leq n < 100\)，\(1 \leq u \leq m < v \leq n\)，同一组配对关系只会给出一次。

解题思路

显然二分图匹配问题，可用 Dinic 解决。

我们将源点连向所有外籍飞行员，权值为 \(1\)；将所有英国飞行员连向汇点，权值为 \(1\)；将外籍飞行员连向英国飞行员，权值为 \(+\infty\)。然后跑一边最大流就可得出答案了。

对于求匹配方案，我们只需要看外籍飞行员连向英国飞行员的边有没有经过的流量即可。

代码演示

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
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>

struct Node {
    std::vector<struct Edge> e;
    std::vector<struct Edge>::iterator c;
    int id, l;
};

struct Edge {
    Node *s, *t;
    int c, f, r;

    Edge(Node *s, Node *t, int c, int r) : s(s), t(t), c(c), f(0), r(r) {}
};

inline void addEdge(Node *s, Node *t, int c) {
    s->e.emplace_back(s, t, c, t->e.size());
    t->e.emplace_back(t, s, 0, s->e.size() - 1);
}

struct Dinic {
    std::vector<Node> &nodes;

    Dinic(std::vector<Node> &nodes) : nodes(nodes) {}

    bool level(Node *s, Node *t, int n) {
        for (int i = 0; i <= n; i++) {
            nodes[i].c = nodes[i].e.begin();
            nodes[i].l = 0;
        }

        std::queue<Node *> q;
        q.push(s);

        s->l = 1;

        while (!q.empty()) {
            Node *u = q.front();
            q.pop();

            for (auto &[u, v, c, f, r] : u->e) {
                if (f < c && !v->l) {
                    v->l = u->l + 1;
                    if (v == t) return true;
                    else q.push(v);
                }
            }
        }

        return false;
    }

    int find(Node *s, Node *t, int limit = INT_MAX) {
        if (s == t) return limit;

        for (auto &e = s->c; e != s->e.end(); e++) {
            auto &[u, v, c, f, r] = *e;
            if (f < c && v->l == s->l + 1) {
                int flow = find(v, t, std::min(limit, c - f));
                if (flow) {
                    f += flow;
                    v->e[r].f -= flow;
                    return flow;
                }
            }
        }

        return 0;
    }

    int operator()(int s, int t, int n) {
        int res = 0;
        while (level(&nodes[s], &nodes[t], n)) {
            int f;
            while ((f = find(&nodes[s], &nodes[t])) > 0) res += f;
        }
        return res;
    }
};

int main() {
    int m, n;
    scanf("%d %d", &m, &n);

    std::vector<Node> nodes(n + 2);
    for (int i = 1; i <= n; i++) nodes[i].id = i;

    int u, v;
    while (scanf("%d %d", &u, &v) != EOF && u != -1 && v != -1) {
        addEdge(&nodes[u], &nodes[v], INT_MAX);
    }

    for (int i = 1; i <= m; i++) addEdge(&nodes[0], &nodes[i], 1);
    for (int i = m + 1; i <= n; i++) addEdge(&nodes[i], &nodes[n + 1], 1);

    Dinic dinic(nodes);

    printf("%d\n", dinic(0, n + 1, n + 1));
    for (int i = 1; i <= m; i++) {
        for (auto &[u, v, c, f, r] : nodes[i].e) {
            if (u != &nodes[0] && v != &nodes[0] && u != &nodes[n + 1] && v != &nodes[n + 1] && f) {
                printf("%d %d\n", u->id, v->id);
            }
        }
    }

    return 0;
}