求助昨天 CF E1 O(n^3) 做法

学术版

Deuteron @ 2024-10-07 12:10:10

rt，只会 kruskal 重构树的 O(n^2) 做法。

场上 E1 比 E2 过的人多了几倍，有理由推测存在其他做法。

by fzitb7912 @ 2024-10-07 12:13:14

@Deuteron 会了 O(n^2) 又何必学 O(n^3)。

by fzitb7912 @ 2024-10-07 12:13:40

@harmis_yz 我也不会 O(n^3)，只会 O(n^2)。

by maokaiyu @ 2024-10-07 12:14:41

@Deuteron Floyd 求路径上的权，然后贪心依次加点，计算答案。

by Deuteron @ 2024-10-07 21:21:17

@maokaiyu 为什么贪心是对的

by maokaiyu @ 2024-10-08 13:59:48

@Deuteron 因为权值是取 max，不会存在选择两个不怎么优的B、C,比选择之选一个更优秀 A 要好。