2 maoxunxing maoxunxing 于 2014.12.07 00:23 提问

快速求最大流和最小割?

今天看一段英文介绍最大流的。其中有一段不是很明白。
文章地址:http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

不明白的那段:
In fact, we have solved another problem that at first glance would appear to have nothing to do with maximum flow in a network, ie. given a weighted directed graph, remove a minimum-weighted set of edges in such a way that a given node is unreachable from another given node. The result is, according to the max-flow min-cut theorem, the maximum flow in the graph, with capacities being the weights given. We are also able to find this set of edges in the way described above: we take every edge with the starting point marked as reachable in the last traversal of the graph and with an unmarked ending point. This edge is a member of the minimum cut.

我理解到的程度是:
这段大致意思是说能一眼把最小割的边找到?前部分是说去掉最小流量的边(去掉的边一定是最小割的一部分?)。然后我就看不明白了。。。

求看得懂得指点下。小弟十分感谢····

1个回答

Rocloud
Rocloud   Rxr 2014.12.07 17:43

http://www.cnblogs.com/Booble/archive/2011/03/04/1970453.html

网络流(一) {基本概念与算法}

不知是否有你需要的内容呢

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!