http://code.activestate.com/recipes/tags/stoer_wagner/2009-09-19T07:16:58-07:00ActiveState Code Recipes2009-09-19T07:16:58-07:00Shao-chuan Wanghttp://code.activestate.com/recipes/users/4168519/http://code.activestate.com/recipes/576907-minimum-cut-solver/

<p style="color: grey"> Python recipe 576907 by <a href="/recipes/users/4168519/">Shao-chuan Wang</a> (<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/ford_fulkerson/">ford_fulkerson</a>, <a href="/recipes/tags/mininum_cut/">mininum_cut</a>, <a href="/recipes/tags/min_cut/">min_cut</a>, <a href="/recipes/tags/stoer_wagner/">stoer_wagner</a>). </p> <p>A Minimum Cut Solver</p> <p>This python script is for solving the ACM problem Q2914: Minimum Cut. <a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2914" rel="nofollow">http://acm.pku.edu.cn/JudgeOnline/problem?id=2914</a></p> <p>Instead of using Ford-Fulkerson method, I use Stoer and Wagner's Min cut Algorithm. <a href="http://www.cs.dartmouth.edu/%7Eac/Teach/CS105-Winter05/Handouts/stoerwagner-mincut.pdf" rel="nofollow">http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/stoerwagner-mincut.pdf</a></p> <p>However I also include the max flow method (from wiki) for benchmark. The code can be found at: <a href="http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm</a></p>