WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
图论部分简介
图论相关概念
图的存储
DFS(图论)
BFS(图论)
树基础
树的直径
最近公共祖先
树的重心
树链剖分
树上启发式合并
虚树
树分治
动态树分治
AHU算法
树哈希
矩阵树定理
有向无环图
拓扑排序
最小生成树
斯坦纳树
最小树形图
最小直径生成树
最短路
拆点
差分约束
k 短路
同余最短路
强连通分量
双连通分量
割点和桥
2-SAT
欧拉图
哈密顿图
二分图
最小环
平面图
图的着色
网络流简介
最大流
最小割
费用流
上下界网络流
Prufer 序列
LGV 引理
弦图
46 objects
本站非官方,所收集资源均来源于网络。
网络流简介 - 图论
网络流在 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 题