b******v
发帖数: 1493 | 1 【 以下文字转载自 Topcoders 俱乐部 】
发信人: bokertov (早上好), 信区: Topcoders
标 题: 找min cut的解有什么简单的算法吗？
发信站: BBS 未名空间站 (Wed Jun 20 17:36:56 2012, 美东)
书上一般先介绍怎样找max flow的解，然后说max flow和min cut的等价定理，不过好
像都没讲怎样具体怎样找min cut的解呀？有没有比较简单的算法？ |
t*****r
发帖数: 324 | 2 就是增广路算法啊，已经够简单了。。。
【在 b******v 的大作中提到】
: 【 以下文字转载自 Topcoders 俱乐部 】
: 发信人: bokertov (早上好), 信区: Topcoders
: 标 题: 找min cut的解有什么简单的算法吗？
: 发信站: BBS 未名空间站 (Wed Jun 20 17:36:56 2012, 美东)
: 书上一般先介绍怎样找max flow的解，然后说max flow和min cut的等价定理，不过好
: 像都没讲怎样具体怎样找min cut的解呀？有没有比较简单的算法？
|
f*********y
发帖数: 376 | 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的解呀？有没有比较简单的算法？
|
b******v
发帖数: 1493 | 4 我只知道怎样用增广路算法找max flow，没有augmentation path时就是max flow了
但是怎样得到max flow对应的min cut呢？
【在 t*****r 的大作中提到】
: 就是增广路算法啊，已经够简单了。。。
|
j*****n
发帖数: 1545 | 5 你够狠！
【在 f*********y 的大作中提到】
: they should ask the max cut and let you find the approximation solution.
|
j*****n
发帖数: 1545 | 6 哪些path saturate 是不是就是1个cut了?
【在 b******v 的大作中提到】
: 我只知道怎样用增广路算法找max flow，没有augmentation path时就是max flow了
: 但是怎样得到max flow对应的min cut呢？
|
b******v
发帖数: 1493 | 7 不是所有saturate的边都在min cut里吧？
【在 j*****n 的大作中提到】
: 哪些path saturate 是不是就是1个cut了?
|
b******v
发帖数: 1493 | |
