网络流基础

定义

网络

有向图 G=(V,E)G=(V,E) 满足

  • 有且仅有一个源点 sVs \in V,有且仅有一个汇点 tVt \in V,且 sts\not = t
  • 有一个函数 c:V×VR+c: V \times V \to R^+ ::success 每一条边对应容量 c(u,v)c(u,v)::
    • 如果 (u,v)E(u,v) \in E(v,u)∉E(v,u)\not\in Ec(v,u)=0c(v,u) = 0

(u,v)(u,v) 可称为

c(u,v)c(u,v) 为弧的容量

可以类比水流,有很多只能单向流水的水管组成网络,水管有粗细 cc

有一个有无限水流进入的源点 ss,和无限水流出的汇点 tt

阅读更多