Bipartite_Graph_and_Network_Flow

发表于 2022-05-04 更新于 2022-05-05 分类于笔记

二分图与网络流

一、二分图相关

二分图判定

定理：一张无向图是二分图，当且仅当图中无奇环。

实现上，黑白染色，$O(n)$ 即可完成判定。

二分图最大匹配

定义：二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

增广路：连接两个非匹配点的路径，匹配边与非匹配边在该路径上交替出现。

性质相关：

长度为奇数。

奇数边是非匹配边，偶数边是匹配边。

路径上匹配边与非匹配边状态取反，新边集仍然是一组合法匹配，且边数增加一。

匈牙利算法：

初始全部非匹配。
寻找增广路并取反，得到更大匹配 $S ^ {\prime}$。
重复步骤 2，直到没有增广路。

具体地，依次尝试给每一个左部点 $x$ 寻找一个右部点 $y$。

$y$ 与 $x$ 匹配需要满足下列条件之一：

$y$ 是非匹配点。
$y$ 与 $x ^ {\prime}$ 匹配，但是 $x ^ {\prime}$ 出发能找到另一个 $y ^ {\prime}$ 与之匹配。

时间复杂度 $O(nm)$。

代码：P3386（Dinic 的板子好像忘记粘了）。

二分图匹配模型

两个要素：

点能分成两个集合，集合内部有 $0$ 条边，简称 $0$ 要素。

每个点只能与 $1$ 条匹配边相连，简称 $1$ 要素。

例题：U64949 棋盘覆盖

被同一骨牌覆盖的两点可以称作被一条边相连，满足 $1$ 要素。
黑白相间染色整个棋盘后，颜色相同的格子不可能连边，即点可分为两部分，满足 $0$ 要素。
剩下就是建图跑最大匹配。

例题：U64970 車的放置

每行每列只能有一个車，因此行与列是满足匹配关系，即满足 $1$ 要素。
行与行直接不存在匹配关系，列与列之间也不存在匹配关系，即满足 $0$ 要素。

特殊二分图匹配

完备匹配：对于一张二分图 $( ( A, B ) , E )$，设其最大匹配为 $E ^ {\prime} $，若 $ | A | = | B | = | E ^ {\prime} |$，则称这张二分图具有完备匹配。

多重匹配：对于一张二分图 $( ( A , B ) , E )$，使 $x \in A$ 最多与 $l _ x $ 条选出的边相连，$y \in B$ 最多与 $r _ y$ 条选出的边相连，则称选出的边为二分图的多重匹配。

求解方法一个是拆点求二分图最大匹配，另一个是网络流。

最优匹配：对于一张二分图，边有边权，所有最大匹配中边权和最大的，被称为最优匹配。

求解方法一般是费用流。

二分图最小点覆盖

图的点覆盖：对于一张无向图 $( V ,E )$，若存在一个点集 $V ^ {\prime} \subseteq V$，且对于任意 $e \in E$，$e$ 至少有一个端点属于 $V ^ {\prime}$，则称 $V ^ {\prime}$ 为这张无向图的一组点覆盖。

二分图最小点覆盖：在二分图中，包含点数最少的一组点覆盖被称为二分图的最小点覆盖。

定理：最小点覆盖包含的点数，等于最大匹配包含的边数。

一个要素：每条边有两个端点，二者至少选择一个。简称 $2$ 要素。

例题：UVA1194 Machine Schedule

满足 $2$ 要素，求最小点覆盖即可。

例题：POJ2226 Muddy Fields

分为行泥泞块和列泥泞块，然后就能分为左部点和右部点。
然后每一块泥地对应一个行块和一个列快，连边。
最后就是求最小点覆盖。

二分图最大独立集

图的独立集：对于一张无向图 $( V , E )$，若存在一个点集 $V ^ {\prime}$，满足 $V ^ {\prime} \subseteq V$，且对于任意 $p , q \in V ^ {\prime}$，都有 $ ( p , q ) \notin E$，则称 $ V ^ {\prime}$ 为这张无向图的一组独立集，包含点数最多的独立集被称为图的最大独立集。

图的团：对于一张无向图 $( V , E )$，若存在一个点集 $ V ^ {\prime}$，满足 $V ^ {\prime} \subseteq V$，且对于任意 $p , q \in V ^ {\prime}$，都有 $ ( p , q ) \in E$，则称 $ V ^ {\prime}$ 为这张无向图的一组团，包含点数最多的团被称为图的最大团。

定理：无向图 $G$ 的最大团，等于补图 $G ^ {\prime}$ 的最大独立集。

对于一般无向图，最大团和最大独立集都是 NPC 问题。

定理：对于一张 $n$ 个点的二分图，设其最小点覆盖数（最大匹配边数）为 $v$，则其最大独立集大小 $u = n - v$。

例题：P3355 骑士共存问题

将棋盘黑白相间染色后，容易发现日字的对角颜色必然相异，即格子可以分为两个点集，满足 $0$ 要素。
将所有日字对角连边之后，求出二分图的最大独立集即可。

例题：P2423 [HEOI2012]朋友圈

原图很难处理，补图很特殊。
图的最大团等于补图的最大独立集。
在补图中，$A$ 的奇数、偶数权值点分别构成完全图，$B$ 的奇数偶数权值点变为二分图的左右两部。
因此 $A$ 中最多选两个点，枚举选出的点 $x,y$（或者不选），然后把 $B$ 中与 $x,y$ 有连边的点删去，在 $B$ 中剩余的点里求最大独立集即可。

有向无环图的最小路径点覆盖

定义：给定一张 DAG，用尽量少的不相交的简单路径覆盖所有点（也就是每个点恰被覆盖一次），这样的路径集合被称为最小路径点覆盖。

拆点二分图：

把每个点拆成编号 $x$ 和 $x + n$ 两个点。

建立一张新的二分图，$1 \sim n$ 是左部点，$ n + 1 \sim 2n$ 是右部点。

对原图的每条有向边 $( x , y )$，在二分图的左部点 $x$ 与右部点 $y + n$ 之间连边。

最终得到的二分图被称为原图的拆点二分图。

定理：设 DAG 的拆点二分图的最大匹配边数为 $v$，则 DAG 的最小点覆盖包含的路径条数 $u = n - v$。

模板：P2764 最小路径覆盖问题

有向无环图的最小可重复路径点覆盖

给定一张 DAG，用尽量少的可相交的简单路径覆盖所有点（也就是每个顶点可以被覆盖多次），这样的路径集合被称为有向无环图的最小可重复路径点覆盖。

处理方法：将原图传递闭包，按最小路径点覆盖的处理方法处理即可。

二、网络流相关

一个网络 $G = ( V ,E )$ 是一张有向图，图中的每条有向边 $( x , y ) \in E$ 都有一个给定的权值 $c ( x ,y )$，称为边的容量。特别地，若 $( x , y ) \notin E$，则 $c ( x , y ) = 0$。图中还有两个指定的特殊节点 $S,T(S \ne T)$，分别被称为原点和汇点。

设 $f( x , y )$ 是定义在节点二元组 $( x , y )$ 上的实数函数，且满足：

容量限制：$f ( x , y ) \le c ( x , y )$。

斜对称：$f ( x , y ) = - f ( y , x )$。

流量守恒：对于任意 $x \notin S, x \notin T$，都有 $\sum _ {( u , x ) \in E} f ( u , x ) = \sum _{ ( x , v ) \in E } f( x ,v )$。

则 $f$ 称为网络的流函数。

对于 $( x , y ) \in E$，$f ( x , y)$ 称为边的流量，$c ( x , y ) - f ( x , y )$ 称为边的剩余流量。

$\sum _ {( S , v ) \in E} f ( S , v )$ 称为整个网络的流量。

最大流

对于一个给定的网络，是整个网络的流量最大的合法的流函数被称为网络的最大流，此时的流量被称为网络的最大流量。

EK 增广路算法

增广路是指从 $S$ 到 $T$ 的一条路径，流过这条路径，使得当前的流量可以增加。

那么求最大流问题可以转换为不断找增广路的问题，并且图中不存在增广路时就达到了最大流。

找增广路时，直接暴力从 $S$ 到 $T$ 广搜即可，从 $S$ 开始不断向外广搜，通过剩余流量大于 $0$ 的边，直到找到 $T$ 为止。

找到增广路之后，记增广路上的最小剩余流量为 $f$，则最大流加上 $f$，增广路上的每一条边的剩余流量减去 $f$，增广路上的每一条边的反向边的剩余流量加上 $f$。

时间复杂度 $O(n m ^ 2)$，实际运用中远远达不到。

一般 $10 ^ 3 \sim 10 ^ 4$ 的数据都是可以处理的。

Dinic 算法

残量网络：在任意时刻，网络中所有节点，以及剩余容量大于 $0$ 的边构成的子图被称为残量网络。

EK 每轮可能会遍历整个残量网络，但是只能找出一条增广路，很浪费。

分层图：将图分层，节点深度 $d _ x$ 表示 $S$ 到 $x$ 最少需要经过的边数。

在残量网络中，满足 $d _ y = d _ x + 1 $ 的边 $( x, y )$ 构成的子图被称为分层图。

显然，分层图是一张 DAG。

算法流程

不断重复下面的步骤，直到残量网络中 $S$ 不能到达 $T$：

在残量网络上 BFS 求出节点层次，构造分层图。
在分层图上 DFS 寻找增广路，在回溯时实时更新剩余容量。另外，每个点可以流向多条出边，同时还加入若干剪枝和优化。

时间复杂度 $O( n ^ 2 m )$，不加剪枝和优化的复杂度是错的。

一般 $10 ^ 4 \sim 10 ^ 5$ 的数据都是可以处理的。

模板：P3376。

最大流解决二分图多重匹配

新建一个源点 $S$ 和一个汇点 $T$，从 $S$ 向每一个左部点 $x$ 连一条容量为 $l _ x$ 的边，从每个右部点 $y$ 向 $T$ 连一条容量为 $r _ y $ 的边。

把原二分图的每条边看作从左部点到右部点连的一条容量为 $1$ 的边。

那么二分图的最大多重匹配就等于该网络的最大流。

Dinic 在由二分图通过上述方法构造出来的网络中时间复杂度为 $O( m \sqrt{n } )$，比匈牙利算法快，实际表现更优。

二分图最大匹配的必须边与可行边

必须边即最大匹配中必然出现该边。

可行边即最大匹配中可能出现该边。

下面是这两种边的判定方法。

最大匹配是完备匹配
把二分图中的非匹配边看作从左部向右部的有向边，匹配边看作从右部到左部的有向边，构成一张新的有向图：
- 必须边 $( x, y )$：$( x , y )$ 是当前二分图的匹配边，且 $ x , y $ 在新的有向图中属于不同的强连通分量。
- 可行边 $( x , y )$：$( x , y )$ 是当前二分图的匹配边，或 $x , y$ 在新的有向图中属于同一个强连通分量。
最大匹配不一定是完备匹配
- 必须边 $( x, y )$：$( x , y )$ 的流量为 $1$，且 $x , y$ 在残量网络上属于不同的强连通分量。
- 可行边 $( x , y )$：$( x , y )$ 的流量为 $1$，或 $x , y$ 在残量网络上属于同一个强连通分量。

最小割

给定一个网络 $ G = ( V , E )$，源点为 $S$，汇点为 $T$。

若一个边集被删去之后，$S$ 与 $T$ 不再连通，则称该边集为网络的割。

边的容量之和最小的割被称为网络的最小割。

最大流最小割定理：最大流等于最小割。