CF1515F Phoenix and Earthquake
简述题意
有一个无向连通图，每个店上有一些沥青，修复一条边需要 x 吨沥青，修复一条边后沥青可以随意移动，问使整个图联通的修复顺序。
分析
首先沥青总数不到 \(x(n - 1)\) 的一定不行，对于总量大于它的，我们断言一定可以。
归纳地说，我随便选择一条可以修复的边修复它，那么问题会转化为 n - 1 的情况，而最后只剩两个点时一定是可以的。
P2619 [国家集训队] Tree I
简述题意
无向带权图，有一些边是白边，一些是黑边，需要选出恰好有 k 条白边的最小生成树。
分析
考虑我想要先选择 k 条白边，然后只选黑边。但是选最小的不一定最优，我们去想怎么样可以既满足选 k 条白边，又使答案最小。
考虑一个最小生成树的想法，我跑出来最小生成树，然后看白边比 k 大还是小。如果大了，那么就说明有些白边过于优秀，挤占了黑边的生存空间，我们可以给白边加一个附加权值使之劣一些。
我们也可以换一个角度，从 dp 角度理解，即 \(f_i\) 是选择 i 条白边的最优情况，那么我们的转移就是遍历白边，加入一条未加入白边，同时发现会形成一个环，我们要删掉环上的一条黑边。
那么就是看加入白边后那一条能使得答案变大得最小。
我们可以发现每一次加入边，增加的量一定每次都是不降的，因为我这一次能踹走的黑边，之前一定也有方案踹走。那么我们可以发现这个是有凸性的。
wqs