跳转至

# 网络流简介

本页面主要介绍网络流相关的基本知识．

## 概述

网络（network）是指一个特殊的有向图 𝐺 =(𝑉,𝐸)G=(V,E)，其与一般有向图的不同之处在于有容量和源汇点．

- 𝐸 E 中的每条边 (𝑢,𝑣)(u,v) 都有一个被称为容量（capacity）的权值，记作 𝑐(𝑢,𝑣)c(u,v)．当 (𝑢,𝑣) ∉𝐸(u,v)∉E 时，可以假定 𝑐(𝑢,𝑣) =0 c(u,v)=0．

- 𝑉 V 中有两个特殊的点：源点（source）𝑠 s 和汇点（sink）𝑡 t（𝑠 ≠𝑡 s≠t）．

对于网络 𝐺 =(𝑉,𝐸)G=(V,E)，流（flow）是一个从边集 𝐸 E 到整数集或实数集的函数，其满足以下性质．

1. 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 0 ≤𝑓(𝑢,𝑣) ≤𝑐(𝑢,𝑣)0≤f(u,v)≤c(u,v)；
2. 流守恒性：除源汇点外，任意结点 𝑢 u 的净流量为 0 0．其中，我们定义 𝑢 u 的净流量为 𝑓(𝑢) =∑𝑥∈𝑉 𝑓(𝑢,𝑥) −∑𝑥∈𝑉 𝑓(𝑥,𝑢)f(u)=∑x∈V f(u,x)−∑x∈V f(x,u)．

对于网络 𝐺 =(𝑉,𝐸)G=(V,E) 和其上的流 𝑓 f，我们定义 𝑓 f 的流量 |𝑓||f| 为 𝑠 s 的净流量 𝑓(𝑠)f(s)．作为流守恒性的推论，这也等于 𝑡 t 的净流量的相反数 −𝑓(𝑡)−f(t)．

对于网络 𝐺 =(𝑉,𝐸)G=(V,E)，如果 {𝑆,𝑇}{S,T} 是 𝑉 V 的划分（即 𝑆 ∪𝑇 =𝑉 S∪T=V 且 𝑆 ∩𝑇 =∅S∩T=∅），且满足 𝑠 ∈𝑆,𝑡 ∈𝑇 s∈S,t∈T，则我们称 {𝑆,𝑇}{S,T} 是 𝐺 G 的一个 𝑠 s-𝑡 t 割（cut）．我们定义 𝑠 s-𝑡 t 割 {𝑆,𝑇}{S,T} 的容量为 ||𝑆,𝑇|| =∑𝑢∈𝑆∑𝑣∈𝑇 𝑐(𝑢,𝑣)||S,T||=∑u∈S∑v∈T c(u,v)．

## 常见问题

常见的网络流问题包括但不限于以下类型问题．

- 最大流问题：对于网络 𝐺 =(𝑉,𝐸)G=(V,E)，给每条边指定流量，得到合适的流 𝑓 f，使得 𝑓 f 的流量尽可能大．此时我们称 𝑓 f 是 𝐺 G 的最大流．
- 最小割问题：对于网络 𝐺 =(𝑉,𝐸)G=(V,E)，找到合适的 𝑠 s-𝑡 t 割 {𝑆,𝑇}{S,T}，使得 {𝑆,𝑇}{S,T} 的总容量尽可能小．此时我们称 {𝑆,𝑇}{S,T} 的总容量是 𝐺 G 的最小割．
- 最小费用最大流问题：在网络 𝐺 =(𝑉,𝐸)G=(V,E) 上，对每条边给定一个权值 𝑤(𝑢,𝑣)w(u,v)，称为费用（cost），含义是单位流量通过 (𝑢,𝑣)(u,v) 所花费的代价．对于 𝐺 G 所有可能的最大流，我们称其中总费用最小的一者为最小费用最大流．

我们将在稍后的章节中对它们进行详细介绍．

## 例题：网络流 24 题

网络流 24 题是中文互联网上广泛流传的一个题单（LibreOJ/洛谷），至少在 2010 年前后就已经存在．该题单引入了一些经典的将其他问题建模为网络流问题的技巧．由于时代的局限性，这些问题未必是最具代表性的网络流问题，但仍值得有志于算法竞赛的读者一阅．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, StudyingFather, MegaOwIer, sshwy, Tiphereth-A, MingqiHuang, Nanarikom, Anguei, Chrogeek, EndlessCheng, Enter-tainer, liaoyanxu, Macesuted, ouuan, Xarfa, Xeonacid
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用