网络流简介

网络流在 OI 中是显得尤为重要的。在《算法导论》中就用了 35 页来讲述网络流的知识,在这里,给大家介绍网络流中的一些基本知识。

网络

首先,请分清楚 网络(或者流网络,Flow Network)与 网络流(Flow)的概念。

网络是指一个有向图 G=(V,E)

每条边 (u,v)\in E 都有一个权值 c(u,v) ,称之为容量(Capacity),当 (u,v)\notin E 时有 c(u,v)=0

其中有两个特殊的点:源点(Source) s\in V 和汇点(Sink) t\in V,(s\neq t)

f(u,v) 定义在二元组 (u\in V,v\in V) 上的实数函数且满足

  1. 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即, f(u,v)\leq c(u,v)
  2. 斜对称性:每条边的流量与其相反边的流量之和为 0,即 f(u,v)=-f(v,u)
  3. 流守恒性:从源点流出的流量等于汇点流入的流量,即 \forall x\in V-\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)

那么 f 称为网络 G 的流函数。对于 (u,v)\in E f(u,v) 称为边的 流量 c(u,v)-f(u,v) 称为边的 剩余容量。整个网络的流量为 \sum_{(s,v)\in E}f(s,v) ,即 从源点发出的所有流量之和

一般而言也可以把网络流理解为整个图的流量。而这个流量必满足上述三个性质。

:流函数的完整定义为

f(u,v)=\left\{\begin{aligned} &f(u,v),&(u,v)\in E\\ &-f(v,u),&(v,u)\in E\\ &0,&(u,v)\notin E,(v,u)\notin E \end{aligned}\right.

网络流的常见问题

网络流问题中常见的有以下三种:最大流,最小割,费用流。

最大流

我们有一张图,要求从源点流向汇点的最大流量(可以有很多条路到达汇点),就是我们的最大流问题。

最小费用最大流

最小费用最大流问题是这样的:每条边都有一个费用,代表单位流量流过这条边的开销。我们要在求出最大流的同时,要求花费的费用最小。

最小割

割其实就是删边的意思,当然最小割就是割掉 X 条边来让 S T 不互通。我们要求 X 条边加起来的流量总和最小。这就是最小割问题。

网络流 24 题

LibreOJ

洛谷


评论