跳转至

网络流简介

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

网络流的基本概念

容量：网络中的每条有向边 (x,y)都有一个给定的权值，称为边的容量，记为 c(x,y)。

源点、汇点：网络中的两个特殊节点。流量从源点产生，最后全部归于汇点。源点用 S表示，汇点用 T表示。

流量：对于网络中的每条边 (x,y)， f(x,y)被称为该边的流量。流量需要满足以下三条性质：

  1. 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 f(x,y) \leq c(x,y)。
  2. 斜对称性：每条边的流量与其相反边的流量之和为 0，即 f(x,y)=-f(y,x)。
  3. 流量守恒：从源点流出的流量等于汇点流入的流量。

网络流的常见问题

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

最大流

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

最小费用最大流

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

最小割

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

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论