网络流简介

网络流在 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)\)，即 从源点发出的所有流量之和。

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

注：流函数的完整定义为

网络流的常见问题

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

最大流

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

最小费用最大流

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

最小割

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

网络流 24 题

LibreOJ

洛谷

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用