网络流——概念篇 网络 网络表示一个有向图(可能有环),\(G=(V,E)\) 每条边 \((u,v)\in E\)都有一个权值\(c(u,v)\),称之为容量,对于$(u,v)E \(,均有\)c(u,v)=0$ 其中有两个点: \(s\in V\) 源点(没有入度) \(t\in V\) 汇点(没有出度) 流 设 \(f(u,v)\)定义在二元组 \((u\in V,v\in V)\)上的实数函数且满足 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即,\(f(u,v)\le c(u,v)\) 斜对称性:每条边的流量与其相反边的流量之和为 0,即 \(f(u,v)=-f(v,u)\) 流守恒性:从源点流出的流量等于汇点流入的流量,即 $xV-{s,t}, {{(u,x)E}}f(u,x)={{x,vE}}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)\)即 从源点发出的所 ...