题解：P14146 朝花

· · 题解

首先有一点很容易注意到的是，可以用 9 的代价将 (a,b),(a,c) 两条边变成 (b,c) 一条边或是将 (a,b),(a,c),(b,c) 全部删掉。于是我们就可以一直用 9 的代价删至少一条边，直到每个点的度数小于等于一。代价不会超过 9m。

然后我们思考如果有两条边 (a,b),(c,d) 该怎么删。经过一些观察和构造可以发现，分别选择 \{a,b,c,d\},\{a,b,c\},\{a,b,d\} 就可以删掉，代价为 34。而 (a,b),(c,d) 最多有 \frac{n}{4} 组，所以代价不会超过 \frac{17}{2}n。

最后的问题就是还剩一条边时怎么删。这个其实挺难的，但所幸样例已经给我们了，代价为 88。

所以这样做总代价不会超过 20n+10m+100。