[2010 Asia Regional Fuzhou Problem B Nubulsa Expo]【例题】【Stoer-Wagner算法】【无向图全局最小割】

【地址】http://acm.hdu.edu.cn/showproblem.php?pid=3691

【题目大意】

给定一个无向连通图和一个源点，让你选一个汇点，使得源点到汇点的最大流最小。输出这时的最大流流量。

【算法分析】

实际上就是求全局最小割。给的那个源点是废的，因为如果图被分割开了，无论当前这个源点在那一块，总有一个汇点在另外一块。所以可以无视他给的源点。

然后直接套Stoer-Wagner算法就可以了。

推荐资料：http://www.docin.com/p-48578124.html

6edward_mj2000MS688K1683BG++2011-02-10 17:01:10

这个时间太亮了

【CODE】

http://xiudaima.appspot.com/code/detail/4696014