对于一个s-t平面图，我们对其进行如下改造：
1.n连接s和t，得到一个附加面
2.求该图的对偶图G*：令附加面对应的点为s*，无界面对应的点为t*
3.删去s*和t*之间的边
一条从s*到t*的路径，就对应了一个s-t割！
更进一步，如果我们令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度！
分析一下时间复杂度n新图中的点数和边数都是O(n)的n使用二叉堆优化的Dijkstra算法求最短路，时间复杂度为O(nlog2n)
温馨提示：答案为网友推荐，仅供参考
第1个回答 2011-01-11
什么意思
相似回答