算法找到最小削減給定的最大流量

任何人都可以給我一個想法找到最小切的圖（V，E，c，s，t，f）其中f [v] [w]是最大流量和c [v] [w]是容量？算法找到最小削減給定的最大流量

2012-03-07 user1247412

Google？這裏有很多東西，你到底有什麼問題？ – 2012-03-07 11:44:49

可能的重複[如何使用最大流算法找到圖上的最小切點？]（http://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum-cut-on -a-graph-using-a-maximum-flow-algorithm） – 2012-03-07 11:59:18

這是一個真正的問題。那些關閉它的人不理解最大流最小割定理。 – wcochran 2012-11-16 22:55:00

從源節點運行BFS或DFS。你不能走到右邊的邊緣，坐在最小的切口上。當遍歷邊時，你必須檢查是否c[v][w] > f[v][w]。您可以到達的節點位於最小切割的左側，其他節點位於右側。

來源

2012-03-07 11:49:26

您可以查看更多詳情[here]（http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ctl=1331121392192&ved=0CC4QFjAA&url=http%3A%2F%2Fciteseerx.ist。 psu.edu％2Fviewdoc％2Fdownload％3Bjsessionid％3D6F1324E4CAF290676E3605F39901D1A4％3Fdoi％3D10.1.1.85.7307％26rep％3Drep1％26type％3DPDF＆EI = tkxXT7v-EsrJrAeZwLXzCw＆USG = AFQjCNHlUpzr2bHRgY9ecDnxpKDyRgp9Pw＆SIG2 = 6P1qlsU54JAjBmMVScfd7Q） – 2012-03-07 11:58:52

http://ezekiel.vancouver.wsu.edu/~ cs223/lectures/graphs/maxflow/maxflow.pdf – wcochran 2012-11-16 23:57:22

注意：如果您不想自己實現算法。我會建議你不要，除非你只是想學習，然後使用JGraphT庫。問題解決完美 - MaxFlow和MinCut都通過完美優雅的API交付給您。 – 99Sono 2017-11-29 01:23:05

算法找到最小削減給定的最大流量

回答

相關問題