思考再三还是打算记一下这个玩意。

知识清单/目录：

  • 二分图概念与判定（会）
  • 二分图最大匹配（会）
  • 二分图最大权匹配（不会）
  • Hall 定理（不会）
  • 网络最大流（会）
  • 最小费用最大流（会）
  • 上下界网络流（不会）
  • 网络流扩展与建模举例

1.二分图概念与判定

  • 二分图等价于图可以被黑白染色（二染色）。

    • 二分图黑白染色方案数为 $2^c$，其中 $c$ 是连通块个数。

    • 可以被黑白染色等价于图上不存在奇环。

[HNOI 2019] 校园旅行

首先有一个 $m^2$ 的经典 BFS，从一个点或一个边出发向外拓展出一条回文链。

考虑把图进行重构，对于 $n\ge 2$ 的同色连通块，如果是二分图，只需要保留一棵生成树，否则需要保留一棵生成树+一条奇环，比如一个自环。

证明是显然的，因为我们其实可以只关心一个点到达另一个点所构成的所有路径的奇偶性。大小为 $1$ 的点是不影响的。

2. 二分图最大匹配

  • 二分图匹配最大当且仅当原图不存在增广路。

    • 匈牙利算法：枚举左部点 $1\dots i$，时刻维护该前缀与所有右部点的最大匹配（在线加点），对于新加进来的 $i$，枚举它连出去的所有边，找增广路，找到了 $ans+1$，然后跑路。打一个 vis 数组保证复杂度。

      - 匈牙利算法找到的最大匹配是字典序最大的匹配（以左部点是否匹配为第一关键字），因为它保证每次加入一个点一定不影响原来的左部点的匹配状态。

  • 二分图的最小点覆盖=二分图的最大匹配。

    • 证明：最小点覆盖是最大匹配在线性规划角度上的对偶问题。

      • 构造方式：

        • 求出一组最大匹配

      • 从每个左部未匹配点开始，找一条增广路，将途径的点标记。

      • 取左侧未标记点和右侧标记点作为一组点覆盖。

      • 对于一条边而言，不可能出现左点被标记而右点没有的情况。

      • 对于一条匹配边，它的左点如果被标记则右点一定被标记，如果左点没被标记那么右点一定没有被标记。并且每条非匹配边的两个端点一定至少有一个在一条匹配边上，不在的那一个一定不会被标记。

      • 点覆盖$\ge$ 匹配。

      • 人能看懂的证明：

        • 考虑网络流建图，显然最小割对应最小点覆盖，最大流对应最大匹配。

  • 二分图最大独立集+二分图最小点覆盖=n。

    • 证明：任何一个独立集取补得到且仅得到一个对应的点覆盖。因此点覆盖与独立集是一一对应的。

      • 构造：显然。

  • 二分图最小边覆盖=二分图最大独立集。（没有孤立点）

    • 证明：考虑独立集每个点都需要一个边覆盖它，因此边覆盖>=最大独立集。并且我们掏出来 $m$ 条匹配边，剩下 $n-2m$ 个点每个点都匹配一条边，得到了一个 $n-m$ 的边覆盖，是等于最大独立集的。

  • DAG的最小路径覆盖=n-重构二分图的最大匹配

    • 建一个 $n,n$ 的二分图，如果 $(u,v)\in E$ 则让 $u{left}\to v{right}$。

      • 考虑匹配两个点等价于把它们放在同一条路径上，也就是合并这两条路径。又每个点只能有一个入边和一个出边，所以得证。

  • 二分图最大独立集=补图上的最小团。

    • 这个显然。

  • Dilworth 引理

    • 任意一个偏序集（$a\to b,b\to c\Rightarrow a\to c$） 当中，最长反链=最小链划分（最小不相交路径覆盖）。

      • 注意，一个偏序集会有 $ab\quad a?b$ 四种关系。

导弹拦截

谁能想到！！

问题等价于一个最小链划分，可以变成最长反链问题。

令偏序关系为 $i<j\land a_i\ge a_j$，于是反链就是不下降子序列。

CTSC2008 祭祀

首先传递闭包，得到一个偏序集。

然后直接上 dilworth 引理就做完了吧。

二分图最大权匹配

  • 最小顶标和=最大权匹配

    • 通过线性规划对偶推出来的，大概就是给每个点一个顶标使得一条边两端点顶标和大于等于边权并且顶标和尽可能小。

      • 要求 $\forall w_i\ge 0$，否则把每个边权加上一个大数，最后需要保证最大权匹配是一个最大匹配，如果不保证完美，显然我们把所有负权边干掉是最优的，然后把左右两边边补齐，点补齐。

  • 定义：相等子图表示所有 $ai+b_j=w{i,j}$ 的边构成的子图。

  • 相等子图中如果存在完美匹配，则它为最大权匹配。

    • KM 算法

       - 考虑随便找到一个相等子图（将左侧点点权设为它连出去的最大边，右侧点设为0），然后调整。

      • 具体地，每次将一个左侧点掏出来做最大匹配，如果没有找到就把它扫到的所有点的左权减 $\Delta$，右权加 $\Delta$ 使得可以加一条边到相等子图中。

      • 基于 slack 的优化，有时间再补。

Hall 定理

  • 一个二分图有完美匹配当且仅当任意一个左侧（点数较少）的点集子集映射到右侧的像的大小都大于等于这个子集的大小。

    • 证明：必要性是显然的，充分性可以考虑找到一个没有匹配的左侧点增广，找到的所有点必然恰好构成点集和像，二者相等，所以有一条增广路。（最后一步一定落在右侧点）

  • 推论：一个无向图每个点度数都是 $k$ 称为 $k$ 正则图。那么左右点数相等的 $k$ 正则二分图一定有完美匹配。

    • 考虑随便找一个点集，大小为 $x$，则它的出度为 $kx$，右集合点数最小的时候每个点恰好容纳 $kx$，所以点数也是 $x$。

  • 推广：找到上述左侧子集中最大的子集大小-像大小，记为 $x$，则最大匹配个数为 $|Left|-x$

    • 首先对于这个点集，一定有 $x$ 个点没有匹配，而又因为它是最大的，所以其它点都可以匹配。（不然你把那个点加进来就更大了）。

典中典

左边 $n$ 个点，右边 $m$ 个点，左 $i$ 向右 $[L_i,R_i]$ 连边，求是否存在 $n$ 的匹配。

根据 HALL 定理，我们要找到一个区间 $[l,r]$ 使得里面包含的区间的数量大于 $r-l+1$。

显然扫描线 + 线段树可以做这个事情。

考虑一个贪心，我们把所有区间按照 $r_i$ 排序，考虑第一个左部点匹配谁是最优的。注意到存在 $l_i\le l_1$ 时，匹配哪个点对于 $i$ 无所谓，而存在 $l_1<l_i$ 时，匹配 $l_1$ 最优。因此我们匹配 $l_1$，然后干掉这个匹配点。这个贪心基于让每一个像的大小尽可能减少最小的结论得出的。

典 2

类似典 1，但是 $[1,L_i]\cup [R_i,m]$。

直接上线段树。

典 3

左有 $a_i,b_i$，右有 $c_j,d_j$，$(i,j)$ 有边当且仅当 $a_i\ge d_j\lor c_j\ge b_i$，求最大匹配。

对于一个左集，右集一定是一段前缀的 $d_j$ 和一段后缀的 $c_j$ 的并。于是你可以线段树维护了，我想。

网络最大流

  • Dinic 算法

    • 我们的任务是找所有的增广路。

      • 考虑每次找最短的增广路。

      • 我们 bfs，然后在 bfs 分层的基础上 dfs 找到所有增广路。

      • 复杂度 $O(n^2m)$，二分图上 $O(m\sqrt n)$

SDOI2013 费用流

Bob 的策略是找到流量最大的流然后把它全部改成 $P$。

二分答案，每次把最大的流减少，看一眼跑出来的最大流会不会有变化。

[USACO 07 OPEN] Dining

转化题意为 $n$ 条边，$f$ 个左部点， $g$ 个右部点，二分图最大匹配。

  • 最小割问题

    • 对于一个有向图，每条边有非负权值 $c_i$，求代价最小的一组边集使得删去集合中的边之后 $s,t$ 不连通。

      • 最小割=最大流

      • 证明略了。

      • 最大权闭合子图问题

      • 给出一个 DAG，选 $u$ 必须要一起选 $u$ 的子图里面所有节点，每个点有整数权值。

      • 做法是默认所有正权点都选了。

      • 考虑建一个二分图，左边是正权，右边是负权，把左边每个点能到达的右边的点全部连边跑最小割，答案是总权值 $-$ 最小割。

      • 证明是显而易见的，对于一个正权点，要么你不选它，要么你不选它子图里面所有负点。

      • 最小割求方案。

      • 将参量网络缩点，$(u,v,w)$ 可行当且仅当满流且 $u,v$ 不在同一强连通分量，必经当且仅当满流且 $s,u$ 在一起， $v,t$ 在一起。

最小费用最大流

  • 我们讨论价值不构成负环的费用流问题

  • 求法是每次找到最短路然后流过去。

  • 找最短路只能用 spfa，但是我们可以先跑一 $s$ 到每个点的距离记为 $h_u$，然后置 $(u,v,w)$ 为 $(u,v,w+h_u-h_v)$，每次跑完一遍 dij 之后 $h_u\leftarrow h_u+dis_u$。

  • 模拟费用流

    其实就是带悔贪心，不会，略了。

[CF 280 D] k-Maximum Subsequence Sum

考虑没有修改怎么做。

费用流建图，于是就有模拟费用流做法是选一个最大区间，然后把它取反，做 $k$ 遍然后跑路。

用线段树模拟这个过程即可。

NOI2019 序列

太长不看。

上下界网络流

  • 无源汇上下界可行流

    • 首先我们钦定每条边流满下界，但是这样可能不满足流量守恒。

      • 我们建一个 $S,T$，把所有出流量多的点连到 $T$，把所有入流量多的点从 $S$ 连，把流量设成上界减下界。

      • 算 $S\to T$ 的最大流，如果全部满流意味着存在一个可行流，残量网络上的值就是 $c(u,v)-f(u,v)$ 的值。

  • 有源汇有上下界可行流

    • $T\to S$ 连一个容量 $[0,+\infty]$ 的边就行了。

  • 有源汇有上下界最大流

    • 在残量网络上跑最大流

      • 二分一个 m，把上面那个 $0$ 改成 $m$。

  • 无源汇上下界最小费用可行流

    • 和普通可行流一样做，但是初始费用是下界乘流量。

  • 有源汇上下界最小费用流

    • 可行流就是连一条 $T\to S$。

      • 最大流就是再跑一遍源汇网络流。

      • 或者 binary search

  • 有负环的费用流

    • 考虑把所有负边先流满，然后退流。

网络流建模

直接看 https://www.luogu.com.cn/blog/ix-35/noi-yi-lun-fu-xi-i-er-fen-tu-wang-lao-liu 的最后一部分。