濯茶的前端思考 2014-12-06 16:23 采纳率: 41.2%
浏览 2211

快速求最大流和最小割?

今天看一段英文介绍最大流的。其中有一段不是很明白。
文章地址: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 2014-12-07 09:43
    关注

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

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

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

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题