飞行员配对方案问题

网络流24题题解1

Posted by xv_rong on January 13, 2021

题目描述

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

思路

二分图匹配问题

建立超级源,超级汇点,跑最大流即可。

代码

#include <bits/stdc++.h>
#define fast_io                                                                                                                \
    ios::sync_with_stdio(false);                                                                                               \
    cin.tie(0);                                                                                                                \
    cout.tie(0)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
const int onf = 0xcfcfcfcf;
const int N = (int)1e5 + 5;
const int M = (int)1e5 + 5;
const int mod = (int)1e9 + 7;
const double esp = 1e-8;
//------------天佑AC------------------
struct Edge {
    int v, w, next;
};
struct Dinic {
    vector<Edge> edge;
    vector<int> head;
    vector<int> depth;
    vector<int> cur;
    Dinic(int n) {
        head.assign(n + 1, -1);
    }

    void add_edge(int u, int v, int w) {
        edge.push_back((Edge){v, w, head[u]});
        head[u] = edge.size() - 1;
        edge.push_back((Edge){u, 0, head[v]});
        head[v] = edge.size() - 1;
    }

    bool bfs(int s, int t) {
        depth.assign(head.size(), 0);
        depth[s] = 1;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i = head[u]; i != -1; i = edge[i].next) {
                const Edge &e = edge[i];
                if (!depth[e.v] && e.w) {
                    depth[e.v] = depth[u] + 1;
                    que.push(e.v);
                }
            }
        }
        if (depth[t] == 0)
            return false;
        return true;
    }
    int dfs(int u, int s, int t, int flow) {
        if (u == t)
            return flow;
        for (int &i = cur[u]; i != -1; i = edge[i].next) {
            Edge &e = edge[i];
            if (depth[u] + 1 == depth[e.v] && e.w) {
                int f = dfs(e.v, s, t, min(flow, e.w));
                if (f > 0) {
                    e.w -= f;
                    edge[i ^ 1].w += f;
                    return f;
                }
            }
        }
        return 0;
    }
    int solve(int s, int t) {
        int ans = 0;
        while (bfs(s, t)) {
            cur = head;
            while (int flow = dfs(s, s, t, inf)) {
                ans += flow;
            }
        }
        return ans;
    }
};
int main() {
    fast_io;
    int n1, n2;
    cin >> n1 >> n2;
    Dinic solve(n2 + 2);
    int u, v;
    int m = 0;
    while (cin >> u >> v, u != -1 && v != -1) {
        solve.add_edge(u, v, 1);
        ++m;
    }
    m <<= 1;
    for (int i = 1; i <= n1; ++i)
        solve.add_edge(n2 + 1, i, 1);
    for (int i = n1 + 1; i <= n2; ++i)
        solve.add_edge(i, n2 + 2, 1);
    cout << solve.solve(n2 + 1, n2 + 2) << endl;
    auto &edge = solve.edge;
    for (int i = 0; i < m; i += 2) {
        if (!edge[i].w) {
            cout << edge[i ^ 1].v << ' ' << edge[i].v << endl;
        }
    }
    return 0;
}