洛谷 P2756 飞行员配对方案问题 (二分图匹配)

题目链接：P2756 飞行员配对方案问题

题意

给定 \(m\) 个外籍飞行员和 \(n - m\) 个英国飞行员，每一架飞机需要一名英国飞行员和一名外籍飞行员，求最多能派出几架飞机。

思路

最大流

二分图最大匹配的模板题。

建立一个超级源点 \(s\) 和一个超级汇点 \(t\)。让 \(s\) 与所有的外籍飞行员建立有向边，所有的英国飞行员与 \(t\) 建立有向边。让所有边的容量为 \(1\)，求最大流即可。最后找出所有流量为 \(1\) 的反向边即可。

此题也可以使用匈牙利算法。

代码

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const int N = 500;

const int M = 1e5 + 10;

int head[N], ver[M], edge[M], Next[M], d[N];

int tot, maxflow;

int s, t;

void add(int x, int y, int z) {

    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;

    ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;

}

bool bfs() {

    memset(d, 0, sizeof(d));

    queue<int> q;

    q.push(s); d[s] = 1;

    while(q.size()) {

        int x = q.front(); q.pop();

        for(int i = head[x]; i; i = Next[i]) {

            if(edge[i] && !d[ver[i]]) {

                q.push(ver[i]);

                d[ver[i]] = d[x] + 1;

                if(ver[i] == t) return 1;

            }

        }

    }

    return 0;

}

int dinic(int x, int flow) {

    if(x == t) return flow;

    int rest = flow, k;

    for(int i = head[x]; i && rest; i = Next[i]) {

        if(edge[i] && d[ver[i]] == d[x] + 1) {

            k = dinic(ver[i], min(rest, edge[i]));

            if(!k) d[ver[i]] = 0;

            edge[i] -= k;

            edge[i ^ 1] += k;

            rest -= k;

        }

    }

    return flow - rest;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n, m;

    cin >> m >> n;

    tot = 1;

    s = 0;

    t = n + 1;

    for(int i = 1; i <= m; ++i) add(s, i, 1);

    for(int i = m + 1; i <= n; ++i) add(i, t, 1);

    int u, v;

    while(cin >> u >> v) {

        if(u == -1 && v == -1) break;

        add(u, v, 1);

    }

    int flow = 0;

    while(bfs()) {

        while(flow = dinic(s, inf)) {

            maxflow += flow;

        }

    }

    if(maxflow == 0) {

        cout << "No Solution!" << endl;

        return 0;

    }

    cout << maxflow << endl;

    for(int i = 1; i <= m; ++i) {

        for(int j = head[i]; j; j = Next[j]) {

            if(ver[j] != s && edge[j] == 0 && edge[j ^ 1] == 1) {

                cout << i << " " << ver[j] << endl;

            }

        }

    }

    return 0;

}

参考