P7162 [COCI2020-2021#2] Sjekira 题解

· · 个人记录

思路

要想花费最小，不妨先考虑贪心。

对于权值较大的节点，应该最先断开它与其他节点连接的边，否则，它的权值会多次统计到答案中，不满足最小。

而由于删边较为麻烦，考虑逆序操作，改删边为加边。典型的套路：逆向操作。