濯茶的前端思考 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 关于#python#的问题:求帮写python代码
  • ¥20 MATLAB画图图形出现上下震荡的线条
  • ¥15 LiBeAs的带隙等于0.997eV,计算阴离子的N和P
  • ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
  • ¥15 来真人,不要ai!matlab有关常微分方程的问题求解决,
  • ¥15 perl MISA分析p3_in脚本出错
  • ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
  • ¥15 ubuntu虚拟机打包apk错误
  • ¥199 rust编程架构设计的方案 有偿
  • ¥15 回答4f系统的像差计算