[SMOJ2205]飞行员配对方案问题（二分图最大匹配）

题目描述

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

输入格式 2205.in

文件第 1 行有 2 个正整数 m 和 n 。 n 是皇家空军的飞行员总数 (n<100) ； m 是外籍飞行员数。外籍飞行员编号为 1∼m ；英国飞行员编号为 m+1∼n 。
接下来每行有 2个正整数 i 和 j ，表示外籍飞行员 i 可以和英国飞行员 j 配合。文件最后以 2 个 -1 结束。

输出格式 2205.out

第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M 。

输入样例 2205.in

5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

输出样例 2205.out

4

---

这题是典型的二分图最大匹配问题，虽然也有专门求解这类问题的算法，但也可以直接用我们已学过的最大流解决。

题目的大意是有 m 名外籍飞行员和 (n−m) 名英国飞行员，其中每名外籍飞行员可以与若干英国飞行员配合。要求使外籍飞行员和英国飞行员一一配对驾驶一架飞机，使最终能派出的飞机数最多。

我们可以把外籍飞行员和英国飞行员抽象为两类不同的点，“能配合”的关系则是从代表外籍的点向代表英国的点连一条容量为 1 的边。例如，对于样例：

可以发现一个规律，左边的都是外籍飞行员，右边的都是英国飞行员。左边的点之间互相没有连边，右边的点之间也没有。只有从左边的点连向右边的点的边，这样的图就叫做二分图。选取其中若干边，使任意两条边都不依附于同一个顶点，要求选取尽量多的边，这样的问题就是二分图最大匹配。

不妨把“从左边的点流一个单位的流量到右边的点”视作“左边这个点的外籍飞行员与右边这个点的飞行员合作”，这就是为什么要连边的容量为 1。
那么，要使合作的对数尽可能多，当然就要求流到右边所有点的流量总和最大，而且左边每个点最多只能有一个单位流量发出（不可能同时与多人合作）。
这样的问题我们是无法直接求解的，但可以通过一个小技巧：增加超级源点 s 和超级汇点 t 。从 s 向左边的点都连一条容量为 1 的边，从右边的点都向 t 连一条容量为 1 的边。现在可以认为，一条路径 s→u→v→t 表示外籍飞行员 u 与英国飞行员 v 一起开一架飞机。这样，我们从 s 点可以发出的是不超过 m 个单位的流量，经过最大流算法的匹配，最终流到 t 点的流量就是最多能配对的数量。

参考代码：

//prog81
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 100 + 10;

struct Edge {
    Edge *next;
    int cap;
    int dest;
//  Edge () : next(NULL), cap(0), dest(0) {}
} edges[MAXN * MAXN], *current, *first_edge[MAXN];

int m, n;

void insert(int u, int v, int c) {
    current -> next = first_edge[u];
    current -> cap = c;
    current -> dest = v;
    first_edge[u] = current ++;
//  printf("%d %d\n", u, first_edge[u]);
}

Edge *counterpart(Edge *x) { //求反向边，利用了正反向边在 edges 数组中是相邻储存的特性
    return edges + ((x - edges) ^ 1);
}

bool vis[MAXN];

int dfs(int u, int f) {
//  printf("%d %d\n", u, f);
    if (u == n + 1) return f; //到达汇点，本次增广结束
    if (vis[u]) return 0; else vis[u] = true;
    for (Edge *p = first_edge[u]; p; p = p -> next) {
        int v = p -> dest;
        if (p -> cap)
            if (int res = dfs(v, min(f, p -> cap))) { //找得到一条 u 到 t 的路径，流量为 res
//              printf("%d\n", res);
                p -> cap -= res;
                counterpart(p) -> cap += res;
                return res; //每次找一条
            }
    }
    return 0; //无增广路
}

int main(void) {
    freopen("2205.in", "r", stdin);
    freopen("2205.out", "w", stdout);
    scanf("%d%d", &m, &n); current = edges;
    fill(first_edge, first_edge + n + 1, (Edge*)0);// printf("%d %d\n", m, n);
    for (int i = 1; i <= m; i++) { insert(0, i, 1); insert(i, 0, 0); } //printf("%d\n", first_edge[0]);
    for (int i = m + 1; i <= n; i++) { insert(i, n + 1, 1); insert(n + 1, i, 0); }
    int i, j;
    while (~scanf("%d%d", &i, &j) && i > 0){
//      insert(0, i, 1); insert(i, 0, 0);
        insert(i, j, 1); insert(j, i, 0);
//      insert(j, n + 1, 1); insert(n + 1, j, 0);
    }
    int ans = 0;
    while (true) { //不断增广，直到找不到增广路
        memset(vis, false, sizeof vis);
        if (int res = dfs(0, INF)) ans += res; else break;
    }
    if (!ans) puts("No Solution!");
    else {
        printf("%d\n", ans);
//      for (int i = 1; i <= m; i++)
//          for (Edge *p = first_edge[i]; p; p = p -> next)
//              if (!p -> cap && p -> dest) { printf("%d %d\n", i, p -> dest);/* break;*/ }
    }
    return 0;
}

从这题中可以发现网络流的一个特征，它的题目难点在于“建模”。如何将问题的模型进行转化，从而对网络中的点、边、流赋予具体的含义，是重中之重。
因此，网络流题目的描述将不会再像之前的图论题一样，有非常明显的顶点、边的暗示，而是要靠自己去探索和发现。这就需要多加练习，掌握其中的规律。