AcWing 105. 七夕祭-证明一定存在一个最优解是可以拆成链的

AcWing 105. 七夕祭-证明一定存在一个最优解是可以拆成链的原题链接困难

作者：

东边的西瓜皮 , 2021-12-15 11:34:20 , 所有人可见 , 阅读 1674

23

4

https://www.acwing.com/solution/content/1236/
该篇博客提供的解答很详细，但其中他没有证明一定存在一个最优解是可以拆成链的，所以我在他的基础上补充证明一下。

首先，结论是最优解必不是环状的，而是链状的。
所有有向边都是正值

fvfv1013 2024-01-31 11:56

就差这个了，自己想半天想不明白

dengsh 2023-08-24 00:14

醍醐灌顶，大佬牛逼

acwing_07494 2023-07-18 18:12

厉害，------👍

Lucky_1002 2022-11-30 20:47

太棒了！终于懂了！

魏思远 2022-05-12 09:38

例一那个框的圈不对

Czasn 2022-05-03 21:55

关于类型2
应该是 a-c b+c 和 b+a c-a 吧？

魏思远 2022-05-12 11:20

你讲的对，这是有问题