飞行员配对方案问题

解题思路

每个外籍飞行员都能和若干个英国飞行员匹配，要求我们找出一个匹配数量最多的配对方案。

其实就是一个二分图匹配问题，我们可以用最大流来解决。

首先需要建立一个流网络，一个流网络有一个源点一个汇点，加上 $m$ 个外籍飞行员和 $n$ 个英国飞行员。

每一个外籍飞行员都只能出现在一个匹配里，也就是每一个外籍飞行员只能用一个，这就提示我们连一条从源点到每个外籍飞行员的容量是 $1$ 的边，同理每个英国飞行员也只能用一次，那我们就从英国飞行员向汇点连一条容量是 $1$ 的边。

然后每个外籍飞行员都可以匹配指定的一些英国飞行员，由于每个外籍飞行员和英国飞行员都只能用一次，因此每条边都只能用一个，所以我们可以从每个外籍飞行员向他匹配的所有英国飞行员连一条容量为 $1$ 的边。

综上，我们就建完了整个流网络，并且可以根据任意一种匹配方案构造出一个流，对于这样一个流，每个节点如果被选中，那么流入 $1$，流出也是 $1$，因此流量守恒。并且每条边的容量限制都是 $1$，同样满足容量限制。因此每个流都是一个可行流，所以任何一种匹配方案都能对应一个可行流。

这里需要注意，流量可以是小数，但是对于匹配方案，对应的应该是整数可行流。那么任何一个整数可行流能不能对应到任何一个匹配呢？对于一个可行流，我们把两个点集之间有流量的边全部选出来，那么选出来的匹配就是原问题的一个合法匹配，怎么证明呢，由于是整数可行流，所以每条边不是 $0$ 就是 $1$，并且由于是可行流，所以每个点都是流量守恒的，如果流入的是 $0$，那么流出的也一定是 $0$，说明这个点一定不会在某条匹配边里，如果流入是 $1$，那么流出的也一定是 $1$，说明这个点必然只会在某条边里。

由此得出原问题的任何一个可行解都能对应到流网络的任何一个整数可行流。所以只要知道流网络的整数可行流的最大值，就能知道原问题的最大可行解。

那么我们现在要求的是整数可行流的最优解，但是 Dinic 算法求的是所有可行流的最优解。怎么求出整数可行流的最优解呢，从 Dinic 算法本身出发，可以发现，如果所有边的容量都是整数变量来存，那么就能保证求的所有可行流都一定是整数值可行流。所以整数可行流的最优解一定是所有可行流的最优解，因此直接用 Dinic 算法求所有可行流的最优解即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = 5210, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], w[M], e[M], ne[M], idx; //邻接表
int d[N], q[N], cur[N]; //层数、队列、当前弧

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //搜索从 u 节点往终点传输的最大流量，flow 表示当前传输到 u 节点的流量
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(w[i] && d[j] == d[u] + 1)
        {
            int k = find(j, min(rest, w[i]));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //dinic算法求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

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

    memset(h, -1, sizeof h); //初始化邻接表

    S = 0, T = m + 1;
    for(int i = 1; i <= n; i++) add(S, i, 1);
    for(int i = n + 1; i <= m; i++) add(i, T, 1);

    //建立残量网络
    int a, b;
    while(scanf("%d%d", &a, &b), a != -1) add(a, b, 1);

    printf("%d\n", dinic());

    for(int i = 0; i < idx; i += 2)
        if(e[i] > n && e[i] <= m && !w[i])
            printf("%d %d\n", e[i ^ 1], e[i]);

    return 0;
}