我上下界网络流学假了?
查看原帖
我上下界网络流学假了?
1052693
sangshang楼主2024/1/26 22:40

有源汇上下界最大流不是应该先连一条从 tt 到 ss 的容量为 +∞+\infty 的边,跑一遍最大流(平衡流量)后,先记录下那条 t→st\to s 的容量 +∞+\infty 的边流了多少(即原图在平衡过程中流量多少)。再加上去掉这边后,跑一遍的最大流(获得原图还能被压榨的流量)。

怎么到这题就是直接取第二次获得的最大流。

2024/1/26 22:40
加载中...