[lnsyoj2621/luoguP2756] 飞行员配对问题

题意

给定一侧 \(n\) 个点，一侧 \(m - n\) 个点的二分图，求最大匹配数及一个合法匹配

sol

二分图最大匹配问题。
可以使用匈牙利算法或网络流解决，其中网络流通常更快。
首先建立超级源点 \(S\) 和超级汇点 \(T\)，由于每个点只能与其他点匹配一次，原二分图中的每条边在网络流中容量应为 \(1\)；又因为每个点只能被选择一次，所以向超级源点及汇点连边时，每条边的容量都为 \(1\)。跑最大流即可。
输出方案时，枚举原图的每条边，当该边被选取，即反向边容量非 \(0\) 时，即为一对匹配。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 105, M = 20005, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], ne[M], idx;
int d[N], cur[N];
int n, n1, n2;
int S, T;

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 ++ ;
}

void build(){
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &n1);
    n2 = n - n1; n += 2;
    for (int i = 1; i <= n1; i ++ ) add(n - 1, i, 1);
    for (int i = 1; i <= n2; i ++ ) add(n1 + i, n, 1);
    int a, b;
    while (scanf("%d%d", &a, &b) != EOF) 
        add(a, b, 1);
    S = n - 1, T = n;
}

bool bfs(){
    memset(d, -1, sizeof d);
    queue<int> q;
    d[S] = 0, q.push(S), cur[S] = h[S];
    while (!q.empty()){
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if (j == T) return true;
                q.push(j);
            }
        }
    }
    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]){
        int j = e[i];
        cur[u] = i;
        if (d[j] == d[u] + 1 && f[i]){
            int t = find(j, min(limit - flow, f[i]));
            if (!t) d[j] = -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(){
    build();
    printf("%d\n", dinic());
    for (int i = (n1 + n2) * 2 + 1; i <= idx; i += 2) if (f[i]) printf("%d %d\n", e[i], e[i ^ 1]);
}