二分图最小字典序

,

首先求出任意一个完美匹配。

考虑这样一个问题：对二分图 G，已知它的一个完美匹配 T（匹配中边的集合），如何判定是否存在包含给定边 $e$ 的完美匹配？

  • 如果 $e$ 属于 T，显然是存在的。

  • 否则，存在包含 $e$ 的完美匹配，当且仅当，存在经过 $e$ 的依次经过匹配边、未匹配边的环。判断是否存在这样的环只需要 $dfs $ 一遍即可。复杂度 $O(n+m)$。如果存在，把环上的匹配边变成未匹配边，未匹配边变成匹配边就能得到一个包含 $e$ 的完美匹配。

证明：

充分性：把环上的所有匹配边变成未匹配边，未匹配边变成匹配边就得到了一个包含 e 的完美匹配。

必要性：假设存在包含 e 的完美匹配 T’，设 S 为 T 与 T’ 的对称差，考虑 S 中的边构成的子图 G’。由于 T 和 T’ 都是完美匹配，所以每个点度数要么是 0 要么是 2。因此 G’ 是若干个简单环组成的。显然 G’ 上相邻的两条边不可能都是 T 中的边，也不可能都是 T’ 中的边。考虑经过 e 的环，显然它是一个依次经过匹配边、未匹配边的环。

用以上算法，可以找到从当前图上编号最小的点 $u$ 出发，在保证存在完美匹配的前提下，$u$ 能匹配的编号最小的点，设这个点为 $v$。

注意到，在这个过程中要判断的边 $e$ 的一个端点是固定的，也就是 $u$，所以无需把每个可能的 $v$ $O(n+m) $ 地判断一遍，只需要从 $u$ 出发做一次 $dfs $ 即可。判断的同时也得到了一个包含边 (u,v) 的完美匹配。把这条边删去就得到了一个删除点 $u$ 和 $v$ 后的图的完美匹配。对删除 $u$ 和 $v$ 后的图重复上述过程即可。

总复杂度 $O(n^2+nm)$.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline bool dfs(int x) {
    for (auto y:to[x]) 
        if (cnt!=v[y]) {
            v[y]=cnt;
            if (!match[y]||dfs(match[y])) return match[y]=x,match[x]=y,1;
        }
    return 0;
}
inline int dfs2(int x,int top) {
    for (auto y:to[x]) 
        if (v[y]!=cnt) {
            v[y]=cnt;
            if (match[y]==top||(match[y]>top&&dfs2(match[y],top)>=1)) {
                return match[x]=y,match[y]=x,y;
            }
        }
    return -1;
}

最后 $match_i$ 就是答案

参考知乎 。

例题

NOI2009 变换序列

考虑到每个点只向右边连两个，所以说直接倒着跑一遍匈牙利就好了，似乎用不上这个东西。