飞行员配对方案问题

传送门

题目大意

有一群开飞机的，他们分为英国人和非英国人。对于飞行员的进行搭配，设计一个找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

题目分析

这个题其实是可以用匈牙利算法实现的，时空复杂度\(O(nm)\)，观察数据范围，其实是不会超时的。但是使用dinic则可以在\(O(m √n)\)计算完成。

所以本题采用dinic算法。

首先，第一个问题是如何将其转化为最大流问题。转换成最大流问题，首先要满足两个条件

1. 容量限制

2. 流量守恒

而转化问题的思想，我们可以参考闫氏dp分析法。在一个解决方案集合内找到最优解，然后对应找到可行流。所以当前问题为如何建图。

我们想把整个题按照二分图的想法，分成两个集合，英国人和外籍，之后进行匹配。匹配的时候打上流量和容量。之后在转化为最大可行流问题，在两个集合的左和右两方（一共两方，比如集合一左方和集合二右方）分别建上源点汇点，之后建图的时候边权设置成1就行了。

建完图之后剩下的就和dinic算法差不多了，但这个题还要输出一个方案，这个时候我们只需要对i=0到idx进行遍历输出，但注意，输出的时候由于我们idx在每次建边时跑了两遍，所以i+=2就处理完啦！

代码实现

#include <bits/stdc++.h>
#define rint register int

using namespace std;

const int N = 1e2 + 5;
const int M = 6e3 + 5;
const int INF = 1e8;

int m, n, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}
bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S;
    d[S] = 0;
    cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T)
                    return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}
int find(int u, int limit)
{
    if (u == T)
        return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t)
                d[ver] = -1;
            f[i] -= t;
            f[i ^ 1] += t;
            flow += t;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0, flow;
    while (bfs())
        while (flow = find(S, INF))
            r += flow;
    return r;
}
int main()
{
    cin >> m >> n;
    S = 0;
    T = n + 1;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++)
        add(S, i, 1);
    for (int i = m + 1; i <= n; i++)
        add(i, T, 1);
    int a, b;
    while (cin >> a >> b, a != -1)
        add(a, b, 1);

    cout << dinic() << endl;

    for (int i = 0; i < idx; i += 2)
        if (e[i] > m && e[i] <= n && !f[i])
            cout << e[i ^ 1] << " " << e[i] << endl;

    return 0;
}

总结

在网络流的实际应用中，更看重的是建图的能力，而建图能力是要不断做题磨出来的，之后要熟悉算法实现原理，才能保证题目修改输出条件等情况也可以随心应手的解决。