「BZOJ3118」Orz The Mst
题目链接首先考虑题目描述代表了哪些限制：对于非树边 $(u,v)$ 它在树上对应了一段路径 要求这个路径上每一条边都不比他大。那么贪心的想：树边只可能减小 非树边只可能增大那么我们用 $j \text{ cover } i$ 表示$i$ 树边在 $j$ 非树边两端点在树上的路径上。用 $d_i$ 表示边的变化量。设 $T$ 表示树边集，$E$ 表示非树边集这个问题看起来是个 LP 问题 不妨...
题目链接首先考虑题目描述代表了哪些限制：对于非树边 $(u,v)$ 它在树上对应了一段路径 要求这个路径上每一条边都不比他大。那么贪心的想：树边只可能减小 非树边只可能增大那么我们用 $j \text{ cover } i$ 表示$i$ 树边在 $j$ 非树边两端点在树上的路径上。用 $d_i$ 表示边的变化量。设 $T$ 表示树边集，$E$ 表示非树边集这个问题看起来是个 LP 问题 不妨...