二分图匹配
设二分图G=(V, E)的两个顶点集为X, Y。
- s->Xi,费用为0,按需赋容量。
- Xi->Yj,(Xi, Yj)属于E,费用为边权,按需赋容量。
-
Yj->t,费用为0,按需赋容量。
求(最小费用)最大流。
二分图的最小覆盖集
点权之和最小的覆盖集
- s->Xi,容量为点权。
- Xi->Yj,(Xi, Yj)属于E,容量为inf。
-
Yj->t,容量为点权。
求最小割,由最大流最小割定理,求解最大流即可。
定义不包含容量为inf的边的割为简单割。本网络中,最小割是简单割。
什么叫覆盖集?对于每条边,其两端点至少有一个被选中。割的性质是不连通:任何一条s-t路径上,至少有一条边属于割集。这里所有的s-t路径由3段构成,中间的Xi->Yj容量为inf,不属于简单割。因此,二分图的覆盖集和简单割一一对应。最小割是容量最小的简单割,也是点权之和最小的覆盖集。
对于不带权的二分图图,令所有点点权=1。以这种方式我们求出的是其最小覆盖集,也是其最大匹配。因而,我们证明了König定理:二分图的最大匹配等于最小覆盖。
顶点数最多且点权之和尽量大的覆盖集
- s->Xi,容量为1,费用为点权的相反数。
- Xi->Yj,(Xi, Yj)属于E,容量为inf,费用为0。
-
Yj->t,容量为1,费用为点权的相反数。
求最小费用最大流。
二分图的最大独立集
最小覆盖集和最大独立集是互补问题。
覆盖集:对于每条边,至少选一个端点,即至多不选一个端点。
独立集:对于每条边,至多选一个端点,即至少不选一个端点。
求最大独立集,等价于求其补集,也就是说每条边刨出至少一个端点,并且刨出的点的权和最小,这样才使剩下的最多。|最大独立集|+|最小覆盖集|=所有点的权值之和。
最大权闭合图
设正权点的集合为V+,负权点的集合为V-。
- s->u,u∈V+,容量为点权的绝对值。
- u->v,(u, v)∈E,容量为inf。
-
v->t,v∈V-,容量为点权的绝对值。
求最小割,用正权点减去割的容量即得最大的权。
可行性方面,简单割和闭合图一一对应。设简单割为[S, T],S-{s}即为闭合图中的点。
简单割对应闭合图:反证。假设存在u∈S-{s},v∈T-{t},且(u, v)∈E。因为(u, v)∈E,所以网络N=(V’, E’)中存在(u, v)∈E’且c(u, v)=inf。又因为u, v分属s, t,所以这条边属于[S, T],与简单割的假设矛盾。
闭合图对应简单割:反证。假设[S, T]不是简单割,那么存在u∈S-{s},v∈T-{t},且c(u, v)=inf。这只会当存在(u, v)∈E时发生,与闭合图的假设矛盾。
数量关系方面,最小割意味着最小化“刨开的正权+保留的负权的绝对值”。用正点权之和去减,得到“保留的正权-保留的负权的绝对值=保留的正权+保留的负权”。
有向无环图的最小路径覆盖
- s->Xi,容量为1。
- Xi->Yj,(i, j)∈E,容量上界为1。
- Yi->t,容量上界为1。
DAG的最小路径覆盖=|V|-对应二分图的最大匹配。
约束是什么?对路径的定义中,有至关重要的一点:允许长度为0。于是解的存在性得到了保证。因此,只需满足:对于任意一点,至多有一条与它关联的入边和与它关联的出边被选中。
二分图的匹配,可以从顶点对应的角度看待,也可以从边的角度看待:选出一些边,使得每个顶点至多与一条边关联。和本问题的约束对比,发现有向无环图不是二分图,并且对于顶点而言,边分为入边和出边两类。考虑把点i拆成Xi、Yi,入边连到Yi,出边从Xi出发。这样,问题的约束便和二分图匹配相一致。
目标是什么?使路径覆盖数最小。除了直接数,还能用什么来刻画路径覆盖数?头的数量或尾的数量。什么样的点是头?没有匹配边与对应的Yi关联。尾?没有匹配边与对应的Xi关联。所以,DAG的最小路径覆盖=|V|-对应二分图的最大匹配。
hzwer这儿有另一种更简洁的看待方法:
如果无匹配,显然要n条路径才能覆盖所有点,两个点匹配意味着将可以把它们用一条路径覆盖,路径数就可以减1
我还有一种另类看待方法:
带上下界的网络流。
Step 1
- s->Xi,容量上界为1。
- Xi->Yi,容量下界为1,上界inf。
- Yi->Xj,(i, j)∈E,容量上界为1。
- Yi->t,容量上界为1。
求解s-t最小流。
Step 2
看出一个可行流,于是省去通常求解s-t可行流的步骤。
网络变换为:
- Xi->s,容量上界为1。
- Yi->Xj,(i, j)∈E,容量上界为1。
- t->Yi,容量上界为1。
此网络的t-s最大流与原s-t可行流的叠加,即为原s-t最小流。s-t可行流的值为|V|,用|V|去减t-s最大流即可。
这种看待方法和hzwer的在实质上相同,但是是从形式上的变换得到的。
为什么强调DAG?因为我们只是简单地拆点、匹配,而没有在意这两点是否已经在同一条路径里了。比如,一个环,对应二分图的最大匹配为|V|,实际上,作为一条有始有终的“路径”,它是不能封口的。
最多/最大权不相交路径
最短路
区间k覆盖
- 离散化。
- s->P1,容量为k,费用为0。
- Pi->P(i+1),i
二分法
参考和推荐
- 《线性规划与网络流24题 解题报告》by byvoid
- 《二分图最大匹配的König定理及其证明》by Matrix67
- 《最小割模型在信息学竞赛中的应用》by 胡伯涛