6 年前发表4 年前更新OI / 学习笔记Edmonds-Karp 算法Edmonds-Karp 算法是用来解决最大流和最小费用最大流的常用算法。 ¶ 原理 对于一个图(流量/容量) maxflow 显然最大流为 222阅读更多
6 年前发表4 年前更新OI / 学习笔记网络流基础¶ 定义 ¶ 网络 有向图 G=(V,E)G=(V,E)G=(V,E) 满足 有且仅有一个源点 s∈Vs \in Vs∈V,有且仅有一个汇点 t∈Vt \in Vt∈V,且 s≠ts\not = ts=t 有一个函数 c:V×V→R+c: V \times V \to R^+c:V×V→R+ ::success 每一条边对应容量 c(u,v)c(u,v)c(u,v):: 如果 (u,v)∈E(u,v) \in E(u,v)∈E 且 (v,u)∉E(v,u)\not\in E(v,u)∈E 则 c(v,u)=0c(v,u) = 0c(v,u)=0 (u,v)(u,v)(u,v) 可称为弧 c(u,v)c(u,v)c(u,v) 为弧的容量 可以类比水流,有很多只能单向流水的水管组成网络,水管有粗细 ccc 有一个有无限水流进入的源点 sss,和无限水流出的汇点 ttt 阅读更多