P2756 飞行员配对方案问题

二分图匹配与单位流的同一件事

问题

P2756 飞行员配对方案问题
前 $m$ 名飞行员属于左部，其余飞行员属于右部；一条关系表示两人可以搭档。一名飞行员至多参加一个搭档，要求最大搭档数并输出一种配对。

数据规模：$1\le m\le n<100$，输入关系以 -1 -1 结束。

本题是二分图最大匹配的经典应用。

前 $m$ 名飞行员与其他飞行员天然构成两个集合，每一个搭档关系只连接两个集合中的各一个点，因此正好是一张二分图。

我们在这些关系中选择若干条边，并保证每个飞行员至多出现在一条被选中的边中，这样选中的边集就称为一个 “匹配”。匹配中边的数量就是成功组成的搭档数，因此题目求的就是二分图的 最大匹配。

贪心？

直接找空闲的右部点配对呢？显然这个贪心是不对的，举个反例：

例如关系为 $A-X$、$A-Y$ 与 $B-X$ 时，最优解是 $A-Y$ 与 $B-X$。如果先贪心选择 $A-X$，那么 $B$ 就无法继续匹配。

增广路

相对于当前的匹配，如果一条路径上的边按照 “未匹配边，匹配边，未匹配边 ……” 交替出现，那么它就是一条 交错路。若这条路径从一个未匹配点出发，最终能到达另一个未匹配点，那么就称它为 增广路。

沿着增广路把所有边匹配情况反转，由于两头都是未匹配点，所以这样反转后匹配大小恰好增加 $1$，因此只要仍然存在增广路，当前匹配就还不是最大匹配；当不存在增广路时，根据 Berge 定理，当前匹配就是最大匹配。

匈牙利算法

基于此我们可以设计一个解决这个问题的算法。

依次从左部点出发寻找增广路，通常只记录 match[v]，表示当前和右部点 $v$ 匹配的左部点。

当搜索到右部点 $v$ 时，若它尚未匹配，那就找到了一条增广路，如果 $v$ 已经与某个左部点 match[v] 匹配，就沿当前匹配关系回到 match[v]，尝试让它重新寻找其他右部点。

if( match[v] == 0 || dfs( match[v] ) ) 

第一个表达式表示找到了增广路终点，第二个表达式表示右部点 $v$ 已经被占用，于是沿当前匹配边回到 match[v]，尝试让原来占据 $v$ 的左部点重新寻找其他匹配位置。

注：因此匈牙利算法又被戏称 NTR 算法。

残量网络

二分图最大匹配有一个经典的变形 —— 单位容量流网络的最大流。

连边 $S \to L \to R \to T$，并把所有容量都设置为 $1$，那么每一单位完整流就对应一组匹配，源点和汇点两侧的容量 $1$ 正好就能保证每个点最多被使用一次。

注：这里就会发现，修改源点和汇点两侧容量，就能让对应对象使用不同次数。

巧妙的是，匈牙利算法中的 “让已有的匹配重新找位置”，正好也对应了残量网络中的反向边。

因此可以把匈牙利算法看作单位容量二分网络上的一种特化增广算法：它没有显式维护完整残量网络，而是用 match 数组记录当前匹配，并隐式完成匹配边的反向调整。

显式建立整个网络以后，Dinic 求出的最大流就是最大匹配数。中间关系边若最终流过 $1$，就表示这条搭档关系属于最终匹配。

本题保留匈牙利与 Dinic 两份实现。前者直接利用二分图结构寻找增广路，后者把同一个问题放回一般最大流框架。

▶

P2756 匈牙利

vector<int> adj[maxn];
int match[maxn];
bool vis[maxn];

bool dfs( int u ) {
    for( int v : adj[u] ) {
        if( vis[v] ) continue;
        vis[v] = true;
        if( match[v] == 0 || dfs( match[v] ) ) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

void solve( ) {
    int m = read( ), n = read( );
    while( 1 ) {
        int u = read( ), v = read( );
        if( u == -1 && v == -1 ) break;
        adj[u].push_back( v );
    }

    fill( match, match + maxn, 0 );
    int ans = 0;
    for( int i = 1; i <= m; ++ i ) {
        fill( vis, vis + maxn, false );
        if( dfs( i ) ) ++ ans;
    }
    cout << ans << '\n';

    for( int v = m + 1; v <= n; ++ v ) {
        if( match[v] ) {
            cout << match[v] << " " << v << '\n';
        }
    }
}

▶

P2756 网络流

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

void solve( ) {
    int m = read( ), n = read( );

    int S = 0, T = n + 1;
    init( T );

    for( int i = 1; i <= m; ++ i ) {
        add_edge( S, i, 1 );
    }

    for( int i = m + 1; i <= n; ++ i ) {
        add_edge( i, T, 1 );
    }

    while( 1 ) {
        int u = read( ), v = read( );
        if( u == -1 && v == -1 ) break;
        add_edge( u, v, 1 );
    }

    ll mxflow = Dinic( S, T, n + 1 );

    printf( "%lld\n", mxflow );

    for( int u = 1; u <= m; ++ u ) {
        for( int id : adj[u] ) {
            auto [v, c] = edge[id];
            if( v > m && v <= n && c == 0 ) {
                cout << u << " " << v << '\n';
                break;
            }
        }
    }
}