admin 的博客
网络流/二分图相关笔记(干货篇)
admin LV 10 SU @ 2026-7-10 11:03:24

网络流/二分图相关笔记(干货篇) 更新于 2026/6/21 00:43:49 作者

command_block

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

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

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|)$ 称之为完美匹配。

$\color{blue}\text{定理:}$ 不妨设 $|X|\leq |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$ 集中至少增加一个点.

$S$ 集内部的点,整体 $D$ 变化而“相对高度”不变,①仍然成立。由于我们取了最小值,所有 $S\rightarrow T$ 的边也仍然满足①。

若仍然无法找到增广路,则再次调整 $D$ 即可。

注意找到增广路时,费用为 $D[T]-D[S]$ 才对。若图含有负权,初始化需要一次SPFA。

不难发现,由于也是沿着最短路增广,算法行为和EK相同,时间消耗主要在调整 $D$ 上。

最坏情况下,可能需要 $O(n)$ 次 $O(m)$ 的调整才能找到一条新的的增广路,由于SPFA复杂度上界也是 $O(nm)$ ,所以两个算法在最差情况下复杂度是相同的。

不难发现,当增广路较短(调整数次即可打通),图较为稠密(打通一条边可以大幅扩展 $S$ 集),费用小(可能会有多条边同时被打通)的时候,zkw具有明显的优势。

反之,若增广路较长,费用范围大,图较为稀疏,则zkw由于调整的常数较大(可能远大于SPFA),跑不过EK。(这种情况下同样也存在大量可以把EK卡飞的办法)

~~EK的好处就是很多人写,出题人不敢卡,zkw被卡了出题人可以摆手不管。~~

这玩意听起来玄学写起来倒挺短的。

#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;
}

评测记录

图轻度稠密。由于数据随机,增广路应该较短。权值范围较大。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$

同样也满足条件。

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

$h$ 每次增加的值不会超过 $n*W$ ，最终的值也就在 "流量 $\times n\times$ 边权" 级别的。

评测记录

拆位消圈

还有一种复杂度比较严格的算法是拆位消圈的算法。

注意到当所有边的容量 $\times 2$ ,则最大流的容量也会 $\times 2$ ,总费用同样会 $\times 2$ 。

我们从二进制的高位向着低位考虑,每次将容量的一位加入,则相当于把所有边的费用 $\times 2$ ,然后加上 $0$ 或者 $1$ 。

现在的问题就是对某些边容量 $+1$ ,求费用流。这样的 $+1$ 操作是 $O(m\log C)$ 次的。

我们可以维护 $S$ 集,看看新加入的边是否“跨越”了当前的割,这样才跑。

复杂度是 $O(nm^2\log C)$ ,实际上松松松~

突然发现要消负环,先留坑。Link

最大费用任意流 & 正费用最大流

注意到上述费用流算法的共性,每次都会走最长路(注意是最大费用流),使得最长路逐渐缩短。

这个的证明可以模仿普通 EK,不难直观感知。

对于最大费用任意流,由于费用一直在减小,当单次费用为负时直接不流即可。

正费用最大流指在满足总费用为正的情况下,尽量多流。

由于费用一直在减小,总费用是凸的,当总费用为负时直接不流即可。注意最后一次增广可能无法获得增广路中全部流量。

带有负环的费用流问题 ： P7173 【模板】有负圈的费用流

此时我们直接跑 SPFA 可能造成死循环.zkw的几个基本假设会产生矛盾。

有消负环的办法,不过太玄学了,来日再补罢。

这里介绍一个比较初等的办法,感谢 myh 神仙教育Orz。

需要先学习后面的上下界网络流,才能理解下面的内容。

首先,对于所有负权边强制满流,可能存在流量不守恒的情况。

我们模仿上下界网络流,记录偏差了多少流量,连源汇进行调整。

这里起到调整作用的“差网络”只能退掉前面的流,以及流上没有被强制的流。

对于前面被强制的流,我们建立反向边来退流,由于退得越少越好,所以费用是负数(毫无违和感)。原图未被强制的的边仍然保留。

形式化地讲,以 $(u,v,[f,f],-c),(v,u,[0,f],c)$ 来替换原图中的 $(u,v,[0,f],-c)$ 。

能够发现,新的网络中不再有负环,所以直接跑最小费用流就可以了。

听起来特别美好,其实会有一些奇怪的bug。

会破坏图的特殊结构,比如类二分图转化之后就有可能不是二分图了。
最大流量可能会变成 $\sum f$ 级别(而非题目中原有的限制),若复杂度依赖于流,可能会导致变慢。

#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. 无源汇有上下界可行流

无源汇流 : 满足流量平衡即可,大概是几个“涡流”。

设某条边的流量区间是 $[L,R]$ .

因为每条边都有下界,我们先令每条边流最 $L$ ,称之为“初始流”。

此后,每条边还能在不超过上界的情况下继续流,可以构造一个差网络,令边权为 $R-L$ ,为能额外流的流量。最终在差网络上的流量称作附加流。

我们的初始流不一定满足流平衡,我们就要通过适当地调整差网络使得两个网络的流量加起来平衡。这样我们就构造出了一个可行的循环流。

现在我们就变成了一个差网络上的流问题,只是每个点并不是要求流量守恒,而是要求流量等于给定的数好与初始网络抵消。

我们查看每个点的初始流量代数和 $s$ 。

如果是正数,则在差网络上需要负数的流。而源点具有负数的流,所以这个点要当源点。

如果是负数,则差网络上需要正数的流。而汇点具有正数的流,所以这个点要当汇点。

多元多汇钦定流量,只需要采用超级源超级汇即可,为了方便我们统一称之为 SS,TT。

我们在 $\text{(SS,TT)}$ 之间跑一次普通的有源汇最大流,查看每条源汇边是否流满,都满了则有解。

原网络的流量就相当于初始流+附加流。

评测记录

有源汇上下界可行流

接下来我们要填上源汇,分别称为S,T.

可是我们只会求循环流,能不能让这个环经过 $(S,T)$ 呢?

考虑在 $T\rightarrow S$ 建立一条边,权值为 $\text{INF}$ ,可以理解为“电源内部电流从负极流向正极”。

然后,一个包含这条边的循环流即为有源汇上下界可行流。流量就是该边(可以称之为源汇边或者“电池边”)的流量。

个人觉得还挺好理解的。没有题目所以不放代码了。

有源汇上下界最大流

上面我们已经得到了可行流,下一步就令人吃鲸了。

直接在 $(S,T)$ 之间的差网络上跑最大流即可。

一次最大流可以认为是对差网络的调整,而且使得每个点的流量不变,仍然符合条件。

评测记录

有源汇上下界最小流

想不到吧,还有最小流。

仍然是先求出可行流,把电池边删掉,在 $(T,S)$ 之间的差网络上跑最大流,称之为“退流”。

为啥要删掉电池边?不删掉的话,退流的时候能经过这条无穷大边,显然不对劲,可以称之为“短路”。

理性理解就是此时加电池边不是等价操作,去掉之后由于源汇不守恒仍然是合法的。不管电池边里面装了啥,外面也还有相应的环,所以不会丢失信息。

然后把原来的流量减去退掉的流量则得到答案。(一般默认不能从 $T$ 流到 $S$ ,否则按照定义可能出现负数流量?)

评测记录

另一种方法是二分电池边的容量求解可行流。

有源汇最小费用可行流

没什么好说的,直接把前面的最大流换成费用流即可。注意要预先加上初始流的费用。

有源汇最小费用可行流

具体流程也差不多,但是无源汇的题目很有可能产生负环,需要用到上面那个带负环的费用流。

5.最小割树

P4897 【模板】最小割树（Gomory-Hu Tree）

定义 $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.费用流

4.上下界网络流

无源汇上下界可行流

有源汇上下界可行流

有源汇上下界最大流

有源汇上下界最小流

有源汇最小费用可行流

有源汇最小费用可行流

5.最小割树

状态

开发

支持

关于

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

0.前面的话

1.网络流引入

网络流问题:

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

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

算法

2.网络流相关经典模型

最小割定理

图的基本芝士

二分图相关

闭合子图问题

最小路径覆盖

偏序集的最小链覆盖问题

最长反链问题

3.费用流

4.上下界网络流

无源汇上下界可行流

有源汇上下界可行流

有源汇上下界最大流

有源汇上下界最小流

有源汇最小费用可行流

有源汇最小费用可行流

5.最小割树

状态

开发

支持

关于

还没有账户？

登录

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