digraph dg9 {
v0 -> v1 [label = "4"];
v0 -> v2 [label = "3"];
v1 -> v3 [label = "3"];
v2 -> v4 [label = "4"];
v2 -> v5 [label = "4"];
v3 -> v5 [label = "5"];
v4 -> v6 [label = "2"];
v5 -> v8 [label = "4"];
v6 -> v7 [label = "4"];
v7 -> v8 [label = "3"];
}
对啦这个是我自己写的
至于为什么要写这个呢
是因为昨天我写write_max_flow的时候
0.54秒跑完5000的case而且所有case都跟上面某篇的结果一样
让我非常高兴
但接着我在我旁边的强者开导下
我发现我忘了“一个边上流有flow的时候可以逆向走”这件事
“但是测资结果明明都是对的啊！难道Edmond-Karp算法不用考虑这件事吗？”
....当然没这种好事
所以就诞生了上面的测资
讲了这么多废话
其实只是想提供一个一定要考虑上述情况才能得到max flow的测资
毕竟虽然是不太会犯的错，但万一犯了也无法用测资试出来

原PO是神

一个错的东西跑再快还是错....

推~那这个测资结果应该是多少??

其实自己dot出来就还满明显的 我记得max flow是6吧

推用心 :)

push~

看不是很懂什么叫"一个边上流有flow的时候可以逆向走"@@

以这个图为例的话，应该会先找到0-2-5-8, flow=3 和0-1-3-5-8, flow=1两条path,但其实还有0-1-3-5-2-4-6-7-8其中5-2和原edge方向是反的，因为有flow时可以cancellation