anyone interested to discuss about the last question in ACM this year? <Tunnels
登录 | 论坛导航 -> 华新鲜事 -> 求学狮城 | 本帖共有 20 楼,当前显示第 10 楼 : 从楼主开始阅读 : 本帖树形列表 : 返回上一页
作者:bugzzj (等级:2 - 初出茅庐,发帖:13) 发表:2007-09-21 10:29:07  10楼  评分: 
这样可以么?for each node v perform a maximal flow between v and 0 to obtain the minimal cut (=mc); set the key of v to mc and insert it into a Fibonacci heap h; end while(true) v = h.extract_min(); (based on the key) remove v and all edges incident on v; if(node 1 is disconnected from node 0) return v.key; end end
似乎还是不行
1 2
2 0
1 3
3 0
1 4
4 0
1 5
5 0
5 0
5 0
5 0

对min-cut不是很清楚,下面的计算对吗?
MC(1)=4
MC(2)=2
MC(3)=2
MC(4)=2
MC(5)=5

如果是对的,根据你的算法,结果应该是MC(1)=4吧?
不过,先断掉edge 1 5, 然后等一下。可以更好一些。
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版只看此人从这里展开收起列表

本帖共有 20 楼,当前显示第 10 楼,本文还有 N-1 层楼,要不你试试看:点击此处阅读更多 >>



请登录后回复:帐号   密码