基本思路，不断从源到汇找一条可以容纳更多流量的路径，然后增加流量，直到找不到这种路径。
增广路与剩余网络：
剩余网络是一个很虚幻的东西，它的各个点之间都有两条有向边，表示剩余容量。
增广路可以用DFS或者BFS在剩余网络中找到。
这个算法时间复杂度O(VE^2)，不是太好，适用于点数在1000一下的情况。更优算法有Dinic算法和SAP算法。
维基百科上的页面（包含伪代码）：
https://secure.wikimedia.org/wikipedia/en/wiki/Edmonds_karp
No comments:
Post a Comment