logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
找min cut的解有什么简单的算法吗？ (转载)
avatar
找min cut的解有什么简单的算法吗？ (转载)# JobHunting - 待字闺中
b*v
1 楼
【 以下文字转载自 Topcoders 俱乐部 】
发信人: bokertov (早上好), 信区: Topcoders
标 题: 找min cut的解有什么简单的算法吗？
发信站: BBS 未名空间站 (Wed Jun 20 17:36:56 2012, 美东)
书上一般先介绍怎样找max flow的解，然后说max flow和min cut的等价定理，不过好
像都没讲怎样具体怎样找min cut的解呀？有没有比较简单的算法？
avatar
t*r
2 楼
就是增广路算法啊，已经够简单了。。。

【在 b******v 的大作中提到】
: 【 以下文字转载自 Topcoders 俱乐部 】
: 发信人: bokertov (早上好), 信区: Topcoders
: 标 题: 找min cut的解有什么简单的算法吗？
: 发信站: BBS 未名空间站 (Wed Jun 20 17:36:56 2012, 美东)
: 书上一般先介绍怎样找max flow的解，然后说max flow和min cut的等价定理，不过好
: 像都没讲怎样具体怎样找min cut的解呀？有没有比较简单的算法？
avatar
f*y
3 楼
they should ask the max cut and let you find the approximation solution.

【在 b******v 的大作中提到】
: 【 以下文字转载自 Topcoders 俱乐部 】
: 发信人: bokertov (早上好), 信区: Topcoders
: 标 题: 找min cut的解有什么简单的算法吗？
: 发信站: BBS 未名空间站 (Wed Jun 20 17:36:56 2012, 美东)
: 书上一般先介绍怎样找max flow的解，然后说max flow和min cut的等价定理，不过好
: 像都没讲怎样具体怎样找min cut的解呀？有没有比较简单的算法？
avatar
b*v
4 楼
我只知道怎样用增广路算法找max flow，没有augmentation path时就是max flow了
但是怎样得到max flow对应的min cut呢？

【在 t*****r 的大作中提到】
: 就是增广路算法啊，已经够简单了。。。
avatar
j*n
5 楼
你够狠！

【在 f*********y 的大作中提到】
: they should ask the max cut and let you find the approximation solution.
avatar
j*n
6 楼
哪些path saturate 是不是就是1个cut了?

【在 b******v 的大作中提到】
: 我只知道怎样用增广路算法找max flow，没有augmentation path时就是max flow了
: 但是怎样得到max flow对应的min cut呢？
avatar
b*v
7 楼
不是所有saturate的边都在min cut里吧？

【在 j*****n 的大作中提到】
: 哪些path saturate 是不是就是1个cut了?
相关阅读
贡献F家Onsite一题被雷了怎么回答why did you leave your last positionG已经定好了店面如果withdraw有什么影响F和G的blocking period都分别多长？是不是只要公司不明说你什么时候来下一轮面试就意味着没戏了？搞health的Web公司前景如何CMU的MS好申请不？ (转载)FOUNDATIONS OF PEER-TO-PEER COMPUTING有用吗？ (转载)大家都是怎么找实习的， 是内推还是自己网申?Amazon Senior SDE (Seattle) 大概是什么包袱？求个递归复杂度答案[合集] 说说我当年 H1B 和绿卡的经历吧[合集] 急问，这种layoff情况H1B还有效么？？？ 在线等！Java 的大牛办个班吧女朋友来美结婚团聚，找工作身份问题求建议女EE master 求 marvel , freescale内推总结一下我的经历，回报版上。读两个同样专业的MS有多少OPT？水电工程师 (转载)要开始看python和scala了
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。