今天看一段英文介绍最大流的。其中有一段不是很明白。
文章地址: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.
我理解到的程度是:
这段大致意思是说能一眼把最小割的边找到?前部分是说去掉最小流量的边(去掉的边一定是最小割的一部分?)。然后我就看不明白了。。。
求看得懂得指点下。小弟十分感谢····