d*****u
发帖数: 17243 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: daigaku (๑۩۞۩๑), 信区: Programming
标 题: 这个问题有什么好的解法（或现成code）吗？
发信站: BBS 未名空间站 (Thu Jan 26 16:21:01 2017, 美东)
就是个directed graph，weights都是正的
现在要通过去掉一些edge的办法来消除所有cycle
但要去掉的edges的weights之和尽量小 | z**********3
发帖数: 22 | 2
感觉可以用最小生成树来做。。
从大到小排序然后union不同的edge，能够union的都是还没有遇到环的，不能union的
都是环edge而且是环上最小的边。不知道对不对
【在 d*****u 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: daigaku (๑۩۞۩๑), 信区: Programming
: 标 题: 这个问题有什么好的解法（或现成code）吗？
: 发信站: BBS 未名空间站 (Thu Jan 26 16:21:01 2017, 美东)
: 就是个directed graph，weights都是正的
: 现在要通过去掉一些edge的办法来消除所有cycle
: 但要去掉的edges的weights之和尽量小
| c********w
发帖数: 2438 | 3 mst
每次pop出来最大weight
【在 d*****u 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: daigaku (๑۩۞۩๑), 信区: Programming
: 标 题: 这个问题有什么好的解法（或现成code）吗？
: 发信站: BBS 未名空间站 (Thu Jan 26 16:21:01 2017, 美东)
: 就是个directed graph，weights都是正的
: 现在要通过去掉一些edge的办法来消除所有cycle
: 但要去掉的edges的weights之和尽量小
|
|
