二分图匹配的 存在性问题 与 最小字典序问题

网络流

题目

• xsy1648
   最小点覆盖的存在性。
• xsy2023
   边可能存在。
• hdu1281
   一定存在的点。
• codevs1222
   一定存在的点。
• noi2011
• xsy1910

问题1

描述

  对于一个二分图，我们将 $X$ 部的点从 $1$ 到 $n$ 编号，将 $Y$ 部的点从 $1$ 到 $m$ 编号。
  对于一个最大匹配 $\lbrace(1,a_1),(2,a_2),...,(n,a_n)\rbrace$ ，我们定义它的一个生成序列 $P=(p_1,p_2,...,p_k)$ ， 其中 $p_1<p_2<...<p_k$ ， $p_i$ 出现在序列中，当且仅当 $a_{p_i}>0$ 。
  求所有最大匹配中，生成序列 $P$ 的字典序最小的。

  直观理解：在所有最大匹配中，左边的点的编号尽可能小。

分析

  直接进行匈牙利算法，能取就取。

变式

  变式1：$P$ 的字典序最大。
  按照从大到小的顺序。

  变式2：对每个点给定一个估价值，要求估价值总和最小。
  直接按照估价值排序，进行匹配。

问题2

描述

  对于一个最大匹配 $\lbrace(1,a_1),(2,a_2),...,(n,a_n)\rbrace$ ，我们定义它的一个生成序列 $P_2=((p_1,a_{p_1}),(p_2,a_{p_2}),...,(p_k,a_{p_k}))$ ， 其中 $p_1<p_2<...<p_k$ ， $p_i$ 出现在序列中，当且仅当 $a_{p_i}>0$ 。
  求所有最大匹配中，生成序列 $P_2$ 的字典序最小的。

分析

  先从小到大进行一次二分图匹配，保证第一关键字最小。
  然后对于每个匹配点 $p_i$ ，考虑尝试删去 $(p_i,a_{p_i})$ ，看是否能找到更小的（直接一次找必然会找到最小的）。然后将当前点和匹配点都摧毁。

问题3

描述

  给定二分图。
  求多少个点一定在最大匹配中。

分析

  方法1：随机顺序，取交集。
  方法2：对于每个被匹配的点，考虑删去它和对应点 $x$ 的连边，看 $x$ 是否还能增广，如果不能那就一定在。

问题4

描述

  给定二分图。
  求多少个点可能在最大匹配中。

分析

  随机顺序，取并集。
  这道题是逗你玩的。
  所有有邻边的点都可能在最大匹配中。
  这是因为，首先，最大匹配中的点可能在最大匹配中。然后，不在最大匹配且有连边的点，它出发可以找到一条交错轨，将交错轨的相邻点换一下就好了。

变式

  变式1：所有不可能在最大匹配中的点。

  变式2：所有可能在最大匹配中，不一定在最大匹配中的点。
  可能 减去 一定。

问题5

描述

  给定二分图。
  求多少条边一定在最大匹配中。

分析

  方法1：随机顺序，取并集。
  方法2：求强连通分量。一条两端颜色不同的边。

问题6

描述

  给定二分图。
  求多少条边可能在最大匹配中。

分析

  方法1：随机顺序，取交集。
  方法2：我们对所有匹配边从 $X$ 连向 $Y$ ，非匹配边从 $Y$ 连向 $X$ ，所有两个点在一个强联通分量内的点，或者原本的匹配边，可能在最大匹配中。

变式

  变式1：可能但不一定在最大匹配中的边
  所有两端在一个强连通分量的边。

小结

  对于二分图的问题，有一些比较高级的手段：
① 我们考虑求一次残留网络，考虑用残留网络中的边进行替换。常需要用到 强连通分量（边） 或者 尝试删边（点） 的思想；
② 应用 Hungary算法 基于枚举的点的顺序。我们进行 random_shuffle 。