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