最大流问题 | caojiangxia

[caojiangxia]

https://caojiangxia.github.io/MaxFlow/#more

最大流问题最大流问题是算法竞赛中经常考察的问题，其目标是解决这样一类问题：给定源点$s$和汇点$t$，给定包含源点汇点的网络，网络中每条边有其相应的所能经过的最大流量，求源点至汇点最多能有多少流量。用数学语言描述为： 给定有向图$G(V,E)$ $V$表示点集 $E$表示边集，其中每条单向边由三元组组成，$(from,to,cap)\in E$。表示起点、终点、每条边的容量。 给定源点$s$，汇

[CodeShaoNian]

Dinic 最后每条边的实际分配流量怎么计算呢

[caojiangxia]

@CodeShaoNian
Dinic 最后每条边的实际分配流量怎么计算呢

还是一样的呀，同一层的最短路，每条最短路的顺序是无所谓的。依次减掉相应最短路的最小流量，增加反向边就行。