网络流

概念

$V$:点集 $E$:边集

$G=(V,E)$:图

$S$:源点 $T$:汇点

对于每条边$(u,v)$,有容量$c(u,v)$和流量$f(u,v)$,满足$0\leq f(u,v) \leq c(u,v)$

性质

$1、$容量限制:$f(u,v)<=c(u,v)$

$2、$反对称性:$f(u,v)=-f(v,u)$

$3、$流量平衡:$\sum f(u,i)=\sum f(i,v)$

满足以上三个性质,称为可行流

最大流

流量最大的可行流

残量网络

定义残量网络的流量$r(u,v)=c(u,v)-f(u,v)$

即一条弧还能流过的流量

增广路

残量网络中一条由$S$到$T$的路径

增广路定理:设$flow$是$G$的一个可行流,若不存在增广路,$flow$即为最大流

前向弧&后向弧

分别表示残量网络与退流网络

增流&退流

推进和修正流量

last

最大流的正确性依赖于它的每一条 $S-T$ 流都与一种实际方案一一对应

Isap算法

marks

$1.d[i]$:$i$到$T$的最短距离,可以$bfs$预处理(似乎没有并什么用)
$2.GAP$优化:当$S$和$T$不联通时不存在增广路,可以直接退出循环
$num[x]$表示$d[i]=x$的节点数量,初始化$num[0]=$总节点数
$3.$当前弧优化:保存一个点已经尝试过的邻接边
之前处理过的邻接边是不需要重新处理的(残量网络中的边只会越来越少)
$last[i]$表示当前弧的编号

时间复杂度

上界:$O(n^2m)$
容量均为1:$O(min(n^{2/3},m^{1/2})*m)$
二分图:$O(\sqrt{n} m)$

详解

费用流

每条边除流量限制外还有费用$c$,每流一个单位流量就要增加$c$的费用

一般是最小费用最大流或最小费用可行流

$spfa$单/多路增广

最小割

边集$C$使得$V$中的点分为两部分

割的容量

割中弧的流量总和

最大流最小割定理

一个$S-T$流的最大流等于其$S-T$最小割的容量

判定

跑出最大流后,在残量网络上跑$Tarjan$,求$SCC$

  • 一条满流边$(u,v)$可以出现在最小割集中,当且仅当$u$,$v$不在一个$SCC$中
  • 一条满流边$(u,v)$必定出现在最小割集中,当且仅当$u$与$S$在一个$SCC$里,并且$v$与$T$在一个$SCC$里
  • 易知$S$与$T$一定不在一个$SCC$中

最小割树

任意两点之间的最小割,不同的只有$n-1$个,它们构成一个最小割树

定理$1$:$mincut(a,b)\geq min${$mincut(a,c_1),mincut(c_1,c_2),…,mincut(c_k,b)$}
定理$2$:令$(s,t)$是$(u,v)$在树上简单路径的所有边中$mincut$最小的,那么$mincut(u,v)=mincut(s,t)$

求解方法
  • 随便找两个点作为$S$和$T$,跑$mincut$
  • dfs划分出$S$集和$T$集,更新答案
  • 递归处理$S$集和$T$集

上下界网络流

分类

  • 无源汇
    除$S$、$T$都要求满足流量平衡

  • 有源汇
    所有点都要求满足流量平衡

无源汇可行流

建图

  • 建立附加源点$ss$和附加汇点$tt$
  • 连边:$(u,v,up-down)$
  • 记$d(i)=\sum down(x,i)-\sum down(i,y)$
  • 若$d(i)>0$,连边$(ss,i,d(i))$,否则连边$(i,tt,-d(i))$

求解方法

  • 跑$ss$到$tt$的最大流
  • 若满流,那么一定存在一种可行流
  • 此时,原图中每一条边的流量应为新图中对应的边的流量$+down$

有源汇可行流

建图

  • 在原图中添加一条边$(T,S)$,流量限制为$[0,INF]$,即让$S$和$T$也满足流量平衡条件,改造成无源汇的网络流图

求解方法

  • 同无源汇可行流

有源汇最大流

建图

  • 同有源汇可行流

求解方法

  • 跑有源汇可行流
  • 再跑一次$S$到$T$的最大流,即为答案

有源汇最小流

建图

  • 同无源汇可行流

求解方法

  • 跑$ss$到$tt$的最大流
  • 添加$(T,S)$,流量限制为$[0,INF]$
  • 再跑一次$ss$到$tt$的最大流,判断是否存在可行流
  • 答案即为$(T,S)$的实际流量

有源汇最小费用可行流

建图

  • 建立附加源点$ss$和附加汇点$tt$
  • 连边:$(u,v,up-down,cost)$
  • 记$d(i)=\sum down(x,i)-\sum down(i,y)$
  • 若$d(i)>0$,连边$(ss,i,d(i),0)$,否则连边$(i,tt,-d(i),0)$
  • 添加$(T,S)$,流量限制为$[0,INF]$,费用为$0$

求解方法

  • 跑$ss$到$tt$的最小费用最大流
  • 答案即为(求出的费用+每条边的$down*cost$)

建模

  1. 多源多汇
    增加超级源汇$S’$和$T’$
    连边:$(S’,S,INF),(T,T’,INF)$

  2. 结点容量
    设结点$x$的结点容量为$c$
    将结点$x$拆成$x_{in}$和$x_{out}$
    连边:$(x_{in},x_{out},c)$
    把到达$x$的弧改为到达$x_{in}$,从$x$出发的弧改为从$x_{out}$出发

  3. 最大权闭合子图
    从带点权图$G$中选出一个子图,对于$V$中任意一个结点,其后续节点都在$V$中,最大化$V$的权值和
    连边:$(S,i,c_i),c_i>0$,$(i,T,-c_i),c_i<0$,$(u,v,INF)$
    $ans=$正权点和-最小割

  4. 最大密度子图
    从$G$中选出一个子图,最大化$\frac{|E|}{|V|}$
    考虑$01$分数规划,二分答案为$k$
    将边作为左侧顶点,权为$1$:点作为右侧顶点,权为$-k$
    根据边和点的依赖关系转化成最大权闭合子图,$ans>0$则增大$l$

  5. 最小割建图
    先累加所有收益,再最小化舍弃值
    一般拆成$S$集和$T$集考虑,对应两种选择。这样就会带来冲突,也就是需要割的边
    $check$不同情况,检验建图正确性

Tips

技巧

  • 枚举&二分答案

  • 合并流量
    将起点终点相同的边流量累加起来

分享到: