网络流/二分图相关笔记(干货篇)

command_block · 2020-05-29 13:54:45 · 算法·理论

备忘 : 随机化一般图最大匹配

请配合 : 网络流/二分图相关笔记(应用篇) 食用

0.前面的话

网络流作为一个玄学算法,其题目难度主要在构图上。

至于网络流本身的算法模板,(如果不精细要求复杂度的话)实现起来难度不大。

在此就不多讲模板的实现了,只简单讲讲我对网络流的理解,如果模板部分看不懂建议先找别的文章学习。

本文内容:

主要是模板。

网络流模型的构建
- 性质 : 流量守恒,反对称性,流量范围
- 基本结构 : 增广路,反向边,残量网络
- 与线性规划的关系 (咕咕咕)
几种常见最大流算法以及复杂度说明
- Ford-Fulkerson
- Edmonds–Karp
- Dinic (包括一些奇怪的优化)
关于网络流/二分图的常见模型
- 二分图 : 匹配 , 最小点覆盖 , 独立集 , Hall定理
- 最小路径覆盖
- 闭合子图问题
- 偏序集 : 最小连覆盖 , 最长反链
费用流
- EK费用流
- zkw费用流
- 消圈费用流 (咕咕咕)
- 带有负环的费用流
- 费用流与凸性的关系 (咕咕咕)
上下界网络流
- 上下界无源汇可行流
- 上下界有源汇可行流
- 上下界有源汇最大流
- 上下界有源汇最小流
- 上下界有源汇费用可行流
- 上下界无源汇费用可行流
最小割树及部分证明

1.网络流引入

我们这一节的目标就是切掉 P3376 【模板】网络最大流 ,并且要尽量跑得快些。

网络流问题:

想象一些有向的水管,每个水管都有固定的流量上限,有源点可以出水,有汇点可以收水,问汇点单位时间最多可以收到多少水。

一些性质\large{\color{red}*}

设f[u,v]为u向v流的流量,c[u,v]为u\rightarrow v的容量限制,S为源点,T为汇点。

1.f[u,v]<=c[u,v],即每个水管的流量不能超过限制(废话)

2.f[u,v]=-f[v,u],称为反对称性

注意,如果u\rightarrow v有x的流量,那么f[u,v]=x;\ f[v,u]=-x

即:v\rightarrow u有-x的流量,这服从物理上的相对性,也方便了我们分析性质。

(个人认为反对称性是最重要的)

3.\sum\limits_{v} f[u,v]=0

即每个点流入和流出的流量相同,简称流量守恒(当然源点和汇点不满足)

但是显然,源点流出多少,汇点就流入多少,所以\sum\limits_{u,v} f[u,v]=0

只要满足上述性质,就是个合法的流,读者可以自行验证一下。

也就是说我们成功地把水流问题抽象成了数学模型。

我们的目标就是让\sum\limits_{v}f[S,v]尽量大。

增广路,残量网络与反向边

我们设r[u,v]为残量网络,初始时r[u,v]=c[u,v]。

几次操作之后r[u,v]=c[u,v]-f[u,v],也就是每条边剩余的容量。

容易发现由于\sum\limits_{v}f[u,v]=0,所以\sum\limits_{v}r[u,v]=\sum\limits_{v}c[u,v]是不会变化的。

找到残量网络中从S到T的一条路径,其中的边容量都不为0,这称为一条增广路。

(为什么叫做增广路呢,因为水顺着这条路流过去,就可以增加目前流量啊)

然后把最大流加上这些边的最小容量,再把这些边的容量都减去这个值,相当于更新了一次残量网络。

增广一次不只让正向的边流量增加了,还让反向的边流量减少了。

具体来说,假如增广路中有u\rightarrow v,我们不仅要让f[u,v]+=c,还要让f[v,u]-=c以满足流量平衡。

所以r[u,v]-=c;\ r[v,u]+=c.

这显得比较魔幻:有些边(剩余)的容量反而变大了?

这有一个绝妙的解释,如果一个流流过本次容量变大的边(即反向边),相当于撤销本次流量,即反悔操作。

反复寻找增广路,直到找不到为止,此时得到的就是最大流。\large{\color{red}*}

为什么呢?考虑反证法: 假如还有更大的流,那么肯定会有增广路,口胡如下:

我们的流对应的数值是\sum\limits_{v}f[S,v],假如有更大的流,至少会有一个f[S,v]会变大。

那么相应地,至少会有一个f[v,S]会变小,破坏了守恒性质,为了满足v点的流量守恒,有某个或者多个f[v,u]会变大,且u≠S(不妨只考虑其中一条)

相应地f[u,v]会变小,为了满足守恒性质将会有f[u,v2]会变大,且v2≠v,v2≠S,否则就留成一个圈,流量总和未改变,还是不满足守恒性质。

如此传递下去,假如没有传到T就不满足性质,如果传到了T就必然是一条增广路。

算法

设n为图的点数,m为图的边数。

1.Ford-Fulkerson(FF)

非常直觉的算法,直接dfs寻找增广路,找到就增广,找不到为止。

这个算法的复杂度是多少?会不会一直能找到增广路而陷入死循环呢?

由于最大流明显有限,每次增广当前流量必然增加,实际上是不会陷入死循环的。

但是dfs被出题人随便骗着玩啊,所以复杂度是 O(m*\text{最大流量}) 的。

原因就是每次寻找增广路需要 O(m) ,需要找 O(\text{最大流量}) 次(基本超时铁了)。

值得注意的是,FF算法在二分图上跑的时候,表现很类似匈牙利算法。

虽然这个算法价值不大,还是要多说几句 : 如果某道题目中最大流量很小,可以按顺序依次加边,在残量网络上继续增广,会得到 O(m*\text{最大流量}) 或者 O(n*\text{最大流量}) 的上界,可能比(二分之后)多次建图要快。

2.Edmonds–Karp(EK)\large{\color{red}*}

在FF的基础上,改用bfs找增广路(忽略容量为0的边)。

然而,复杂度神奇地变得与值域无关了,变成了O(nm^2)

原因 : 使用bfs找到的必然是当前含边数最少的一条增广路,找一次需要O(m)的时间。

假如要利用反向边的话,必须走到一条边的尽头再往回走,这样一定比当前的最短路要大,所以是不会产生的,这样子我们就不用考虑容量改变的反向边。

每条增广路都有一个瓶颈,而两次增广的瓶颈不可能相同,所以增广路最多 m 条。

而增广路的长度是[1,n],这就证明了EK的复杂度是O(nm^2),实际上只有一个m是紧的。

3.Dinic\large{\color{red}*}

这玩意实现起来难度不大,~~跑起来松松松~~,实战中应用最广。

首先,建立bfs最短路DAG(成为分层操作),然后只走DAG上的边一次dfs多路寻找增广路,当找不到的时候再次分层。

如何判断一条边u\rightarrow v是否在最短路DAG上:dis[u]+1==dis[v]

同EK,同一个分层图中增广路不超过m条。

多路增广,就是找到了一条增广路之后不马上停止,剩余的容量试试下一条边,经过下面的优化,一次多路增广复杂度是O(nm)。

一次多路增广能够找到当前DAG中的所有增广路,迫使增广路变长(边数变多)。

那么要分n次层,复杂度就是O(n^2m)。有些选手会写单路增广,这样子复杂度是不对的。

优化:

当前弧优化

记录每个点已经试过了哪些流不出流量的边,下次来就不试了,可以把一次多路增广复杂度严格控制在O(nm)内。

证明 : 增广次数为O(m),每次增广最多经过O(n)个点,总复杂度为O(nm)。

不写这个优化,复杂度是错的,可能会退化成 O(nm^2)。
点优化

假如从一个点流不出流量,则把该点的dis变为-1,这样这一次多路增广再也不会来了。

大多数情况下这只能优化常数,但是在某些毒瘤题里面跑的很快。
不完全bfs优化

注意到我们bfs到T之后就可以停止了,因为后面的路径一定更长。

在随机数据,增广路较短(如匹配问题)里能起到不错的效果,且不会增大常数。

某些需要退流(只涉及部分残量网络以提高效率)的题目,采用这个优化会有更加玄学的加成。
交替忽略反向边

比较神奇的优化,目前只由@negiizhao巨神卡到O(n^{1.5}m)

首先忽略反向边跑一次完整的dinic,此时已经得到了一个近似的较优解。

(注意这里如果每次把0边删掉,那么一次忽略反向边的dinic复杂度是O(nm))

再考虑反向边重新跑一次多路增广,最后再次分层。

在随机数据里表现极佳,但是代码量略大。

实战中一般用前三个就够了,复杂度是O(n^2m),实际上远远达不到。

注意,由于边都是成对加入,如果使用邻接链表,则编号连续。

访问反向边时可以直接 xor 1 ,这样要把开始编号设为 2。

如果是 vector 写法,只能大力记下反向边的编号。

Code:

加上{多路增广,当前弧优化,点优化,不完全BFS优化}的dinic: (最常用标准版)

下面是邻接链表的写法,需要vector写法请查看评测记录。

#include<cstdio>
#include<queue>
#define Maxn 10500
#define Maxm 200050
#define INF 1000000000
using namespace std;
int n,m,S,T;
struct Line
{int nxt,t,cap;}l[Maxm];
int tl=1,fir[Maxn],dis[Maxn],cur[Maxn];
void addLine(int f,int t,int cap){
  l[++tl]=(Line){fir[f],t,cap};fir[f]=tl;
  l[++tl]=(Line){fir[t],f,0};fir[t]=tl;
}
bool bfs()
{
  static queue<int> q;
  for (int i=1;i<=n;i++)
    {cur[i]=fir[i];dis[i]=0;}
  q.push(S);dis[S]=1;
  while(!q.empty()){
    int u=q.front();q.pop();
    for (int i=fir[u];i;i=l[i].nxt)
      if (l[i].cap&&!dis[l[i].t]){
        dis[l[i].t]=dis[u]+1;
        if (l[i].t==T){
          while(!q.empty())q.pop();
          return 1;
        }q.push(l[i].t);
        }
  }return 0;
}
int dfs(int u,int flow)
{
  if (u==T)return flow;
  int sum=0;
  for (int &i=cur[u];i;i=l[i].nxt)
    if (dis[l[i].t]==dis[u]+1&&l[i].cap){
      int sav=dfs(l[i].t,min(flow,l[i].cap));
      if (sav){
        l[i].cap-=sav;
        l[i^1].cap+=sav;
        sum+=sav;flow-=sav;
        if (!flow)return sum;
        }else dis[l[i].t]=-1;
      }
  return sum;
}
int main()
{
  scanf("%d%d%d%d",&n,&m,&S,&T);
  for (int i=1,f,t,cap;i<=m;i++){
    scanf("%d%d%d",&f,&t,&cap);
    addLine(f,t,cap);
  }int ans=0;
  while(bfs())ans+=dfs(S,INF);
  printf("%d",ans);
  return 0;
}

评测记录(vector) & 评测记录(邻接链表)

图比较稠密的时候vector快(耗时可低至邻接链表的50%~75%),模板题中数据水且点较多,vector建图常数大体现不出优势。

加上{多路增广,当前弧优化,点优化,不完全bfs优化,交替忽略反向边}的dinic:

评测记录 : Loj#127. 最大流加强版 (差一个点就卡过去了……)

2.网络流相关经典模型

并不一定需要先完全掌握,可以跳过一部分,先去做题。

最小割定理

有源汇割 : 一个边集,删去之后使得源汇不连通,而且其中任意一条边不割,则造成源汇连通(割是紧的)

有源汇最小割 : 一个有向图,边有边权(一般为正),要求割去权值和最小的边集使得源汇不连通。

\color{blue}\text{定理:}

\text{最小割} = \text{最大流}

\color{blue}\text{证明:}

①最大流 \leq 最小割

首先根据割的定义,所有的流都必然经过割边集中的某一条边,那么流量总和最大就是割边集总和。
②最大流 \geq 最小割

考虑我们求出了一个最大流,那么某些边会成为瓶颈,即残量网络上为0.

这些边一定分布成为一个割,否则仍然会有增广路。

最小割的构造 :

跑完最大流之后,从原点选取非0边BFS,把这些点成为S集。

一端在S集一端不在的边即为最小割。

例题① : P4662 [BalticOI 2008]黑手党

这题可以割点而不能割边,我们把点拆成出点入点,中间相连的边为点权即可。

评测记录
例题② : P4126 [AHOI2009]最小割

最小割的可行边和必须边(所有割集的交集和并集)

题解 P4126 【[AHOI2009]最小割】

图的基本芝士

图的匹配 : 选出某些边,使得每两个边没有公共端点。
图的独立集 : 选出某些点,使得每两个点没有连边。
图的点覆盖 : 选出某些点,每条边都至少有一个端点被选择。
闭合子图 : 有向图的子图,满足没有指向子图外的出边。
图的路径覆盖 : 在DAG上用(边)不相交的简单路径覆盖所有的节点。

二分图相关

二分图 : 分为两个部分的图(称为左部和右部),同一个部分内没有边。
二分图判定 : 充要条件 : 没有奇环。 dfs染色判定即可。
二分图最大匹配 : 二分图中边最多的匹配(可能有多种方案)。
P3386 【模板】二分图匹配

网络流建模方法见第三节。当然也可以用二分图专用算法解决。

另附 : Dinic 算法解决二分图匹配的复杂度上界是 O(m\sqrt{n}) 的,一般快于朴素的匈牙利算法。

可见 Itst : Dinic 二分图匹配 / Hopcroft-Karp 算法复杂度简单证明

二分图最小点覆盖 :

\color{blue}\text{定理:}

\text{最小点覆盖}=\text{最大匹配数}

理解&构造 :

①二分图角度

首先,最大匹配中的 a 条边是独立的,所以覆盖这些边都必须要 a 个点。

我们称有匹配边相连的点为匹配点,反之为空点。

对于一个二分图的最大匹配,原图的任意一条边都不可能两端都是空点,否则可以在匹配中加入这条边。

所以,我们只考虑匹配边端点的一个子集就能够覆盖所有空点。

①对于每条匹配边,我们选且只选一个端点。

②而一端是匹配点一端是空点的边,必选匹配点。

这两项是不会产生矛盾的,如果一条匹配边两端都被②钦定要选,就造成了 0-1=1-0 的增广路,这与最大匹配相悖。

构造方法就是先根据②钦定,未被钦定的匹配边就随意选取一端。
②网络流最小割角度

我们发现,建立二分图匹配模型之后,该图的最小割正好对应着点覆盖 : 对于一条中间的 \inf 边,左右至少割一个端点。

那么通过最小割定理就能自然地引出结论。我们查看那些边被割掉了,也容易构造。(某些优化建边的题目只能这样构造)

例题 : UVA1194 Machine Schedule

二分图最大独立集

\color{blue}\text{定理:}

\text{最大独立集}=\text{总点数}-\text{最小点覆盖(集合)}

理解&构造 : 先求出点覆盖集合,取补集则得到最大独立集。

独立 : 如果补集之间有连边,则与点覆盖矛盾。

最大 : 如果这个集合更大,则必然要拆掉点覆盖的一部分,这和“最小”点覆盖矛盾。

总而言之,最大独立集和最小点覆盖是对偶问题。这对一般图也是成立的。

Hall定理

二分图完美匹配 : 若两侧点集为 X,Y , 匹配数达到 \min(|X|,|Y|) 称之为完美匹配。

二分图存在完美匹配$\quad\Longleftrightarrow\quad$对于 $1\leq k\leq|X|$，均满足从 $X$ 选出 $k$ 个不同点，连向 $Y$ 的点集大小 $\geq$ $k

我们称 X 中点集 S 连向 Y 的点集为“邻域”N(S)。

必要性 : 若不满足右侧,则也不满足左侧。

对于某 k 个点,它们连向对面不足 k 个点,显然无法全部匹配。

充分性 : 若不满足左侧,假设其满足右侧。

先构造一种最大匹配,此时有未匹配的点存在。

该未匹配点必然有出边,否则违反右侧。如果出边到达的点也不在匹配中,则可以多匹配一条边,矛盾。

若对面的点存在于匹配中,我们找出与其匹配的点,此时我们拥有两个 X 中的点。

根据右侧, N(S) 中会多出一个点和我们已有的点连边。如果这个点未被匹配,则可以匹配。

若已经被匹配,就会在 X 中引入新的点。

如此可以不断增大集合,然而 X 是有限的,必然导出矛盾。

推论 : 二分图最大匹配为 |X|-\max\big(|S|-|N(S)|\big)

不会用Hall定理来推……

可以把式子变为 \min\big(|X|-|S|+|N(S)|\big) 。

如果建立二分图匹配的网络流模型,把 |X|-|S| 看做左侧割掉的点, N(S) 即为右侧割掉的点,取个 \min 就是最小割。

根据最小割定理得证。(似乎也可以得到经典的Hall定理?)

扩展 : 考虑多重匹配(带容量匹配)的情况,某个点能匹配的次数是W_u。

这可以视作将 u 复制 W_u 次的经典二分图。

我们选择 u 复制出的所有点 S ,要满足 |N(S)|\geq |S|。

不难发现,由于边是相同的, S 中的任意一个元素 x 都满足 N(x)=N(S)。

这样,若 S 满足条件,则 S 的任意子集都满足条件,我们可以把同一个点的复制点集当做整体看待,不妨称作 T_u。

选择原图中左侧的点集 S ,设原图中其邻域为 N(S)。设 W(S)=\sum\limits_{u\in S}W_u

那么在新图中, S 的复制点集大小为 W(S) ,而 N(S) 的复制点集大小为 W(N(S))。

这就引出 : 多重匹配有完美匹配的充要条件 : 对于任意的 S ,均满足 W(S)\geq W(N(S))

闭合子图问题

最大权闭合子图 : 点有点权(可正可负),选出点权和最大的闭合子图。

考虑最小割建模。

对于正价点,连源,边权为点权。对应地,负价点连汇,边权为(负)点权。

原图中的有向边保留,边权置为INF,此时有:

\text{最大权闭合子图}=\text{正点权和}-\text{最小割(构造)}

理解 : 根据结论式子,最小割中割去的边,负权点表示选择,正权点表示不选。

那么我们试图证明 : 在一个割中,割去的负权点和未割的正权点组成的子图W与原图的闭合子图对应。

如果W不是闭合子图,出边可能指向已经割过的正权点或者未割过的负权点。

如果指向未割过的负权点,则W内的流可以通过INF边和该点流向汇,与割矛盾。

如果指向已割过的正权点,则W内的流相当于“越过”这个割,同样矛盾。

类似地,如果W是闭合子图,则W对应的流无法流到汇,与割对应。

构造 : 要求给出闭合子图的方案。

先求出最小割,在闭合子图中的点为 : 未割过的正权点 & 已经割过的负权点。

最小路径覆盖

P2764 最小路径覆盖问题求所含路径数最少的路径覆盖(点不相交)。

\color{blue}\text{定理:}

\text{最小路径覆盖}=\text{总点数}-\text{拆点二分图最大匹配}

我们采用调整的思想。首先将每个点用单独一个路径覆盖,这是合法的。

每合并两条路径,我们的最终路径数就减小1。

我们拆出入点变成二分图,对于图中原有的边,从出点连向入点即可。

某条边被选中,就相当于“串起”了两条已有的路径。(按照最大匹配合并路径即可得知最小路径覆盖)

注意到“单条路径”的限制 : 不能分叉。这跟匹配的“左端点不重复”限制是等价的。

不能多条汇聚,这跟匹配的“右端点不重复”限制是等价的。

所以我们就把最小路径覆盖转化成了二分最大匹配。

评测记录

偏序集的最小链覆盖问题

定义 :

偏序集 : 元素之间存在大小关系,允许不可比(无定义)的情况出现。但是比较一定有传递性,且不能互相矛盾。
链 : 一个子图,任意两个点都可比。(可以跳过一些中间点,不是图论中的链)
反链 : 一个子图,任意两个点都不可比。

能够发现,如果把DAG的有向边看做 > ,那么一定不会互相矛盾。一般来讲,偏序集通常是以DAG的形式给出的。

现在,需要用尽量少且不重的链,覆盖图上的每一个点。

我们先O(n^3)求出传递闭包(充分利用传递性)。此时两个点之间的比较可以跳过中间点。

不难发现,新图中的一条连续路径,就对应着原图的一条链。我们求出最小路径覆盖即可。

最长反链问题

P4298 [CTSC2008]祭祀给出一个部分偏序集,求最长的反链。

\color{blue}\text{定理:}

\text{最长反链大小}=\text{总点数}-\text{最小链覆盖}

可以自行了解 Dilworth 定理。这里只给出下界的构造解。

我们考虑 : 最小链覆盖\longrightarrow最小路径覆盖\longrightarrow二分图匹配。

这个二分图是由出入点和一系列中间的边组成。

注意到有 \text{总}-\text{最小链覆盖}=\text{总}-\text{二分图最大匹配}

求出一个最大独立集 I ,对于一个点 u 如果满足出入点都在 I 内,则将其加入最长反链答案集合 A。

先证明 A 是个反链,如果任意两个点之间有边,则违反了独立集的性质。

现在证明 \text{构造反链大小}\geq\text{总点数}-\text{二分图最大匹配}

把独立集中的点设为黑点,反之是白点。设原图中的点数为n,则二分图中的点数是2n。设匹配数(最小连覆盖数)为 m。

考虑证明这个反链的大小不低于 n-m,结合 Dilworth 定理就得到了正确性。

独立集大小是 2n-m 的,另一方面又等于 |A|+满足 “左部点或者右部点其中一个属于I的u的个数”

后者不会超过 n 所以前者就不低于n-m。

附更为简洁的判定方法 : u的入点在S集内,且出点不在 \Leftrightarrow u在最长反链中。

证明 : 前文提到,充要条件为 : 出入点均在最大独立集内。

注意到最小点覆盖是最大独立集的补集,这条件相当于 : 出入点均不在最小点覆盖内。

回忆 : 最小点覆盖一定是某条匹配边有闲置边相连的那个端点。

考虑入点,由于其与S连通,说明没有流经过入边,也不会造成匹配,自然入点就不是匹配边端点。

考虑出点,一种情况是与世隔绝,自然也不是最小点覆盖。另一种情况是与某条匹配边相邻,但是一定没有额外的闲置边,否则将会能从S到达。

回到题目,若需要判定某个点能否存在于最长反链内,直接钦定这个点,删除与其冲突的点,再跑一次即可。

评测记录

3.费用流

P3381 【模板】最小费用最大流

在送水模型的前提下,每条边都增加了一个费用,每一单位的流量通过都需要付出相应的费用。

现在要在流量最大的情况下使得总费用最小。

不难想到,每次找费用最小的增广路进行增广即可。

可以把 EK 算法中的 BFS 改为 SPFA ,直接跑就好了。

复杂度不太对劲,可以卡到指数级,但是正常的出题人一般不会去卡。

#include<cstdio>
#include<vector>
#include<queue>
#define Maxn 5100
#define Maxm 100500
#define INF 2147483647
using namespace std;
int n,m,S,T;
struct Line
{int nxt,t,cap,l;}l[Maxm];
int fir[Maxn],tot=1;
inline void addLine(int f,int t,int cap,int cost)
{
  l[++tot]=(Line){fir[f],t,cap,cost};
  fir[f]=tot;
  l[++tot]=(Line){fir[t],f,0,-cost};
  fir[t]=tot;
}
int pre[Maxn],lp[Maxn];
int dis[Maxn],flow[Maxn];
bool in[Maxn];
queue<int> t;
int spfa()
{
  for (int i=0;i<=n;i++)
    {dis[i]=INF;flow[i]=0;}
  flow[S]=INF;dis[S]=0;
  t.push(S);in[S]=1;
  while(!t.empty()){
    int u=t.front();
    in[u]=0;t.pop();
    for (int i=fir[u],v;i;i=l[i].nxt)
      if (l[i].cap&&dis[v=l[i].t]>dis[u]+l[i].l){
        dis[v]=dis[u]+l[i].l;
        flow[v]=min(flow[u],l[i].cap);
        lp[v]=i;pre[v]=u;
        if (!in[v]){in[v]=1;t.push(v);}
     }
  }return flow[T];
}
int main()
{
  scanf("%d%d%d%d",&n,&m,&S,&T);
  for (int i=1,f,t,cap,cost;i<=m;i++){
    scanf("%d%d%d%d",&f,&t,&cap,&cost);
    addLine(f,t,cap,cost);
  }int d,ans=0,cans=0;
  while(d=spfa()){
    int u=T;
    while(u!=S){
      int last=pre[u];
      l[lp[u]].cap-=d;
      l[lp[u]^1].cap+=d;
      u=last;
    }ans+=d;cans+=d*dis[T];
  }printf("%d %d",ans,cans);
  return 0;
}

评测记录(邻接链表)

评测记录(vector)

(由于未知的原因,在洛谷用vector会比邻接链表快很多)

zkw

(起因:P3705中差点TLE,观察最优解靠前发现写的都是zkw)

我们发现前面的EK本质上是沿着最短路增广。

仔细思考最短路的定义,设 D[u] 为点 u 的“距离标号”, l(u,v) 为u,v 之间的边权。

则最短路就是需要求解满足如下两个条件的标号。

① D[u]+l(u,v)\geq D[v]
② 对于某个 v ,至少有一个 u 满足 D[u]+l(u,v)=D[v]

我们增广之后,某些边的容量变为 0 ,也就是说不存在了。这不会破坏①,但是可能破坏②。

EK的解决方法是 : 暴力跑一次SPFA。这样没有利用到之前网络的信息,十分浪费。

考虑如下的策略 : 先找到目前能到达的集合,称为 S ,反之称为 T。

查看目前 \sum\limits_{u\in S,\ v\in T}D[u]+l(u,v)-D[v] 的最小值,然后将 S 中所有的D减去这个值。

能够发现我们至少使得有一条边满足了②,S集中至少增加一个点.

若仍然无法找到增广路,则再次调整 $D$ 即可。注意找到增广路时,费用为 $D[T]-D[S]$ 才对。若图含有负权,初始化需要一次`SPFA`。不难发现,由于也是沿着最短路增广,算法行为和`EK`相同,时间消耗主要在调整 $D$ 上。最坏情况下,可能需要 $O(n)$ 次 $O(m)$ 的调整才能找到一条新的的增广路,由于`SPFA`复杂度上界也是 $O(nm)$ ,所以两个算法在最差情况下复杂度是相同的。不难发现,当增广路较短(调整数次即可打通),图较为稠密(打通一条边可以大幅扩展$S$集),费用小(可能会有多条边同时被打通)的时候,`zkw`具有明显的优势。反之,若增广路较长,费用范围大,图较为稀疏,则`zkw`由于调整的常数较大(可能远大于`SPFA`),跑不过`EK`。(这种情况下同样也存在大量可以把`EK`卡飞的办法) ~~EK的好处就是很多人写,出题人不敢卡,zkw被卡了出题人可以摆手不管。~~ 这玩意听起来玄学写起来倒挺短的。 ```cpp #include<cstring> #include<cstdio> #include<vector> #define Maxn 5100 #define INF 1000000000 using namespace std; struct Line{int t,c,l,b;}; vector<Line> g[Maxn]; void adl(int f,int t,int cap,int len){ g[f].push_back((Line){t,cap,len,g[t].size()}); g[t].push_back((Line){f,0,-len,g[f].size()-1}); } int n,m,S,T,D[Maxn],ans,cans; bool vis[Maxn]; int dfs(int u,int lim) { vis[u]=1; if (u==T){ans+=lim;cans-=lim*D[S];return lim;} for (int i=0,v,sav;i<g[u].size();i++) if (g[u][i].c&&D[v=g[u][i].t]==D[u]+g[u][i].l&&!vis[v] &&(sav=dfs(v,min(g[u][i].c,lim)))){ g[u][i].c-=sav; g[v][g[u][i].b].c+=sav; return sav; } return 0; } bool mdf() { if (vis[T]==1)return 1; int z=INF; for (int u=1;u<=n;u++)if (vis[u]) for (int i=0,v;i<g[u].size();i++) if (g[u][i].c&&!vis[v=g[u][i].t]) z=min(z,D[u]+g[u][i].l-D[v]); if (z==INF)return 0; for (int i=1;i<=n;i++) if (vis[i])D[i]-=z; return 1; } int main() { scanf("%d%d%d%d",&n,&m,&S,&T); for (int i=1,f,t,cap,cost;i<=m;i++){ scanf("%d%d%d%d",&f,&t,&cap,&cost); adl(f,t,cap,cost); }D[S]=-INF; do{memset(vis,0,sizeof(bool)*(n+5));dfs(S,INF);}while(mdf()); printf("%d %d",ans,cans); return 0; } ``` [评测记录](https://www.luogu.com.cn/record/32597994) 图轻度稠密。由于数据随机,增广路应该较短。权值范围较大。`zkw`此时表现得略好于`EK`。 - **原始对偶算法** 在某些题目中，边数 $m$ 会达到 $O(n^2)$ 级别。此时复杂度上界为 $O(nm)=O(n^3)$ 的 `SPFA` 和 `zkw` 增广方法将会变得十分低效。此时如果使用朴素的 $\rm Dijstra$ 算法，则可以在 $O(n^2)$ 内完成一次增广了。但是，残量网络中可能存在负权边，不能直接使用 $\rm Dijstra$。考虑给每个点设定一个“势能” $h$ ,并让 $u\rightarrow v$ 的边权由 $len$ 改为 $len+h[u]-h[v]$。由于“势能”的构造方式，不难验证：新图上 $S,T$ 的最短路 $=$ 原图上 $S,T$ 的最短路 $+h[S]-h[T]$。由于 $h[S]$ 和 $h[t]$ 都是常数，没有本质影响，新图的最短路和原图的最短路是可以对应的。现在，我们只需要适当地安排每个点的 $h$ ，使得新图的边权均非负，即可使用 $\rm Dij$ 了。初始时，先使用一次 `SPFA` 求出各个 $dis[u]$ ，然后让 $h[u]=dis[u]$。根据三角不等式：$dis[u]+len\geq dis[v]\Rightarrow len+h[u]-h[v]\geq 0$。满足新图的边权都非负。设 $C[u][v]$ 为 $u\rightarrow v$ 的边权。$C'[u][v]$ 为附加势能之后的边权， $dis'[u]$ 为附加势能之后的最短路。某次增广之后，若加入新边 $v\rightarrow u$ ，则必有 $dis'[u]+C'[u][v]=dis'[v]$ ,即在原来的最短路上。 $\Rightarrow\ dis'[u]+C'[u][v]+h[u]-h[v]=dis'[v]

\Rightarrow\ dis'[u]+h[u]-(dis'[v]+h[v])+C'[u][v]=0

注意到 C'[u][v]=-C'[v][u]。

\Rightarrow\ (dis'[u]+h[u])-(dis'[v]+h[v])-C'[v][u]=0

可见，若将新的 h[u] 设为 dis'[u]+h[u] ，即可满足新增边权非负。

对于原有的边，则有 dis'[u]+C'[u][v]\geq dis[v]

\Rightarrow\ dis'[u]+C[u][v]+h[u]-h[v]\geq dis[v]

\Rightarrow\ (dis'[u]+h[u])-(dis'[v]+h[v])+C[u][v]\geq 0

同样也满足条件。

不难发现，边修正后的边权总是在减小。

[评测记录](https://loj.ac/submission/927918) - **拆位消圈** 还有一种复杂度比较严格的算法是拆位消圈的算法。注意到当所有边的容量$\times 2$,则最大流的容量也会$\times 2$,总费用同样会$\times 2$。我们从二进制的高位向着低位考虑,每次将容量的一位加入,则相当于把所有边的费用$\times 2$,然后加上$0$或者$1$。现在的问题就是对某些边容量$+1$,求费用流。这样的$+1$操作是$O(m\log C)$次的。我们可以维护$S$集,看看新加入的边是否“跨越”了当前的割,这样才跑。复杂度是$O(nm^2\log C)$,实际上松松松~ 突然发现要消负环,先留坑。[Link](https://www.luogu.com.cn/paste/m5jxz737) - **最大费用任意流** & **正费用最大流** 注意到上述费用流算法的共性,每次都会走最长路(注意是最大费用流),使得最长路逐渐缩短。这个的证明可以模仿普通` EK`,不难直观感知。对于最大费用任意流,由于费用一直在减小,当**单次费用**为负时直接不流即可。正费用最大流指在满足总费用为正的情况下,尽量多流。由于费用一直在减小,总费用是凸的,当**总费用**为负时直接不流即可。注意最后一次增广可能无法获得增广路中全部流量。 - **带有负环的费用流问题** ： [P7173 【模板】有负圈的费用流](https://www.luogu.com.cn/problem/P7173) 此时我们直接跑 `SPFA` 可能造成死循环.`zkw`的几个基本假设会产生矛盾。有消负环的办法,不过太玄学了,来日再补罢。这里介绍一个比较初等的办法,感谢 `myh` 神仙教育Orz。 **需要先学习后面的上下界网络流,才能理解下面的内容。** 首先,对于所有负权边强制满流,可能存在流量不守恒的情况。我们模仿上下界网络流,记录偏差了多少流量,连源汇进行调整。这里起到调整作用的“差网络”只能退掉前面的流,以及流上没有被强制的流。对于前面被强制的流,我们建立反向边来退流,由于退得越少越好,所以费用是负数(毫无违和感)。原图未被强制的的边仍然保留。形式化地讲,以$(u,v,[f,f],-c),(v,u,[0,f],c)$ 来替换原图中的 $(u,v,[0,f],-c)$。能够发现,新的网络中不再有负环,所以直接跑最小费用流就可以了。听起来特别美好,其实会有一些奇怪的`bug`。 - 会破坏图的特殊结构,比如类二分图转化之后就有可能不是二分图了。 - 最大流量可能会变成 $\sum f$ 级别(而非题目中原有的限制),若复杂度依赖于流,可能会导致变慢。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #define MaxN 205 #define pb push_back using namespace std; const int INF=2000000000; struct Line{int t,cap,len;}; vector<Line> g[MaxN]; vector<int> b[MaxN]; void adl(int u,int v,int cap,int len){ b[u].pb(g[v].size()); b[v].pb(g[u].size()); g[u].pb((Line){v,cap,len}); g[v].pb((Line){u,0,-len}); } int n,m,S,T,flow[MaxN],dis[MaxN],pre[MaxN],id[MaxN]; queue<int> q; bool in[MaxN]; int spfa() { for (int i=1;i<=n+2;i++){flow[i]=0;dis[i]=INF;} q.push(S);flow[S]=INF;dis[S]=0; while(!q.empty()){ int u=q.front(); in[u]=0;q.pop(); for (int i=0;i<g[u].size();i++){ if (!g[u][i].cap)continue; int v=g[u][i].t; if (dis[v]>dis[u]+g[u][i].len){ dis[v]=dis[u]+g[u][i].len; flow[v]=min(flow[u],g[u][i].cap); pre[v]=u;id[v]=i; if (!in[v]){q.push(v);in[v]=1;} } } }return flow[T]; } int d[MaxN],ans,ans0; void adl2(int u,int v,int l,int r,int len) {d[u]-=l;d[v]+=l;ans+=l*len;if (l<r)adl(u,v,r-l,len);} void build(){ for (int u=1;u<=n;u++){ if (d[u]>0)adl(S,u,d[u],0); if (d[u]<0)adl(u,T,-d[u],0); } } int S0,T0; void EK() { int d; while(d=spfa()){ ans0+=d; ans+=dis[T]*d; for (int u=T;u!=S;u=pre[u]){ int las=pre[u]; g[las][id[u]].cap-=d; g[u][b[las][id[u]]].cap+=d; } } } int main() { scanf("%d%d%d%d",&n,&m,&S0,&T0); adl(T0,S0,INF,0); for (int i=1,u,v,cap,len;i<=m;i++){ scanf("%d%d%d%d",&u,&v,&cap,&len); if (len<0){adl2(u,v,cap,cap,len);adl2(v,u,0,cap,-len);} else adl2(u,v,0,cap,len); } S=n+1;T=S+1;build(); EK();ans0=0; S=S0;T=T0;EK(); printf("%d %d",g[S0][0].cap+ans0,ans); return 0; } ``` # 4.上下界网络流现在每条边不仅有流量上界,还有流量下界。模板是一个很长的故事。 ## 无源汇上下界可行流 [Loj#115. 无源汇有上下界可行流](https://loj.ac/problem/115) - **无源汇流** : 满足流量平衡即可,大概是几个“涡流”。设某条边的流量区间是$[L,R]$. 因为每条边都有下界,我们先令每条边流最$L$,称之为“初始流”。此后,每条边还能在不超过上界的情况下继续流,可以构造一个差网络,令边权为$R-L$,为能额外流的流量。最终在差网络上的流量称作附加流。我们的初始流不一定满足流平衡,我们就要通过适当地调整差网络使得两个网络的流量加起来平衡。这样我们就构造出了一个可行的循环流。现在我们就变成了一个差网络上的流问题,只是每个点并不是要求流量守恒,而是要求流量等于给定的数好与初始网络抵消。我们查看每个点的初始流量代数和 $s$。如果是正数,则在差网络上需要负数的流。而源点具有负数的流,所以这个点要当源点。如果是负数,则差网络上需要正数的流。而汇点具有正数的流,所以这个点要当汇点。多元多汇钦定流量,只需要采用超级源超级汇即可,为了方便我们统一称之为 `SS,TT`。我们在$\text{(SS,TT)}$之间跑一次普通的有源汇最大流,查看每条源汇边是否流满,都满了则有解。原网络的流量就相当于初始流+附加流。 [评测记录](https://loj.ac/submission/783208) ## 有源汇上下界可行流接下来我们要填上源汇,分别称为`S,T`. 可是我们只会求循环流,能不能让这个环经过$(S,T)$呢? 考虑在 $T\rightarrow S$ 建立一条边,权值为 $\text{INF}$,可以理解为“电源内部电流从负极流向正极”。然后,一个包含这条边的循环流即为有源汇上下界可行流。流量就是该边(可以称之为源汇边或者“电池边”)的流量。个人觉得还挺好理解的。没有题目所以不放代码了。 ## 有源汇上下界最大流上面我们已经得到了可行流,下一步就令人吃鲸了。直接在$(S,T)$之间的差网络上跑最大流即可。一次最大流可以认为是对差网络的调整,而且使得每个点的流量不变,仍然符合条件。 [评测记录](https://loj.ac/submission/783239) ## 有源汇上下界最小流想不到吧,还有最小流。仍然是先求出可行流,把电池边删掉,在$(T,S)$之间的差网络上跑最大流,称之为“退流”。为啥要删掉电池边?不删掉的话,退流的时候能经过这条无穷大边,显然不对劲,可以称之为“短路”。理性理解就是此时加电池边不是等价操作,去掉之后由于源汇不守恒仍然是合法的。不管电池边里面装了啥,外面也还有相应的环,所以不会丢失信息。然后把原来的流量减去退掉的流量则得到答案。(一般默认不能从$T$流到$S$,否则按照定义可能出现负数流量?) [评测记录](https://loj.ac/submission/783248) 另一种方法是二分电池边的容量求解可行流。 ## 有源汇最小费用可行流没什么好说的,直接把前面的最大流换成费用流即可。注意要预先加上初始流的费用。 ## 有源汇最小费用可行流具体流程也差不多,但是无源汇的题目很有可能产生负环,需要用到上面那个带负环的费用流。 # 5.最小割树 [P4897 【模板】最小割树（Gomory-Hu Tree）](https://www.luogu.com.cn/problem/P4897) 定义 $Cut(u,v)$ 为**无向**图中 $u,v$ 之间的最小割大小。先来讲构造。对于一张图,先选取任意两点 $u,v$ ,跑一次最小割,将原图分割成 $S,T$ 两个集合。在 $u,v$ 之间连边,边权为 $Cut(u,v)$。(构建最小割树) 递归求解 $S,T$ 内部的边(注意不要使用残量网络,要原图),直到集合内只有一个点。不难发现,我们会得到一个树形结构,称作最小割树。( 这样需要求解 $n-1$ 次完整的最大流 ) 最小割树满足一个很强的性质 : 两点之间的最小割 **等于** 在最小割树上两点间路径中边的最小权。一点点来证明。 - **定理1** 任选 $u,v$ 跑一次最小割,将图分成了 $S,T$ 两个集合。则 $(x\in S,y\in T)\Longrightarrow Cut(x,y)\leq Cut(u,v)

证明 : 割断 u,v 的割显然也分隔了 S,T , 所以 Cut(u,v) 是上界。

定理2 任取三点 a,b,c 则 Cut(a,b),Cut(a,c),Cut(b,c) 中最小值至少出现两次。

证明 : 不妨假设 Cut(a,b) 是最小的,先割开,再讨论 c 在 S,T 的那个集合内。

不妨设其在 S 内,由 {定理1} 得到 Cut(b,c)\leq Cut(a,b) 。

而由Cut(a,b)最小的假设则得到 Cut(b,c)=Cut(a,b) ,出现两次。
- 推论1 : Cut(a,b)\geq \min(Cut(a,c),Cut(b,c))
  
  若 Cut(a,b) 不是最小值,显然成立,若 Cut(a,b) 是最小值,则一定会出现两次,也会出现在 \min 中。
- 推论2 对于两点 (u,v) ,有 Cut(u,v)\geq\min\Big(Cut(u,w_1),Cut(w_1,w_2)...,Cut(w_m,v)\Big)
  
  多次使用 {推论1} 即可。
定理③(最小割树定理) 如上所述。设 u,v 为欲求的两个点, x,y 为路径上的某两个点。

首先,不难得到 u,v 在 x,y 最小割的两侧。由 {定理1} , Cut(u,v)\leq Cut(x,y)。

然后根据 {定理2.2} 又能得到 Cut(u,v)\geq Cut(x,y)。

这就得到了 Cut(u,v)=Cut(x,y) ,鼓掌!

回到模板题,求出最小割树之后,对于每个询问就是树链 \min 问题了,随手搜索/倍增就是。

#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
#define INF 1000000000
#define Maxn 505
#define Maxm 1505
using namespace std;
struct Line{int t,c,b;};
vector<Line> wg[Maxn];
#define g wg
void adl(int f,int t,int cap){
  g[f].pb((Line){t,cap,g[t].size()});
  g[t].pb((Line){f,cap,g[f].size()-1});
}
int n,m,S,T,dis[Maxn],cur[Maxn];
queue<int> q;
bool bfs()
{
  for (int i=1;i<=n;i++){cur[i]=dis[i]=0;}
  q.push(S);dis[S]=1;
  while(!q.empty()){
    int u=q.front();q.pop();
    for (int i=0,v;i<g[u].size();i++)
      if (g[u][i].c&&!dis[v=g[u][i].t]){
        dis[v]=dis[u]+1;
        if (v==T){
          while(!q.empty())q.pop();
          return 1;
        }q.push(v);
        }
  }return 0;
}
int dfs(int u,int flow)
{
  if (u==T)return flow;
  int sum=0;
  for (int &i=cur[u],v;i<g[u].size();i++)
    if (dis[v=g[u][i].t]==dis[u]+1&&g[u][i].c){
      int sav=dfs(v,min(flow,g[u][i].c));
      if (sav){
        g[u][i].c-=sav;
        g[v][g[u][i].b].c+=sav;
        sum+=sav;flow-=sav;
        if (!flow)break;
        }else dis[v]=-1;
      }
  return sum;
}
void clear()
{for (int i=1;i<=n;i++)g[i].clear();}
#undef g
struct Data
{int f,t,c;}s[Maxm];
int dinic()
{
  clear();
  for (int i=1;i<=m;i++)
    adl(s[i].f,s[i].t,s[i].c);
  int ans=0;
  while(bfs())ans+=dfs(S,INF);
  return ans;
}
vector<int> g[Maxn],l[Maxn];
void adl2(int f,int t,int len){
  g[f].pb(t);l[f].pb(len);
  g[t].pb(f);l[t].pb(len);
}
int p[Maxn],sp[Maxn];
void solve(int l,int r)
{
  if (l==r)return ;
  S=p[l];T=p[r];
  int len=dinic();
  adl2(S,T,len);
  int tn=0,mid=l-1;
  for (int i=l;i<=r;i++)
    if (dis[p[i]])sp[++tn]=p[i];
    else p[++mid]=p[i];
  for (int i=1;i<=tn;i++)
    p[mid+i]=sp[i];
  solve(l,mid);solve(mid+1,r);
}
int qt,cut[Maxn][Maxn],*d;
bool vis[Maxn];
void dfs2(int u,int len)
{
  vis[u]=1;d[u]=len;
  for (int i=0;i<g[u].size();i++)
    if (!vis[g[u][i]])
      dfs2(g[u][i],min(len,l[u][i]));
}
int main()
{
  scanf("%d%d",&n,&m);n++;
  for (int i=1;i<=m;i++){
    scanf("%d%d%d",&s[i].f,&s[i].t,&s[i].c);
    s[i].f++;s[i].t++;
  }for (int i=1;i<=n;i++)p[i]=i;
  solve(1,n);
  for (int u=1;u<=n;u++){
    for (int i=1;i<=n;i++)vis[i]=0;
    d=cut[u];dfs2(u,INF);
  }scanf("%d",&qt);
  for (int i=1,f,t;i<=qt;i++){
    scanf("%d%d",&f,&t);
    printf("%d\n",cut[f+1][t+1]);
  }return 0;
}

网络流/二分图相关笔记(干货篇)

0.前面的话

1.网络流引入

网络流问题:

一些性质\large{\color{red}*}

增广路,残量网络与反向边

算法

2.网络流相关经典模型

最小割定理

图的基本芝士

二分图相关

闭合子图问题

最小路径覆盖

偏序集的最小链覆盖问题

最长反链问题

3.费用流