天天看点

非常棒的网络流总结

二分图匹配

设二分图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 胡伯涛