题解：P12007 【MX-X10-T3】[LSOT-4] 全国联赛？

感觉此题可以评蓝。

首先，由 "

n-m-1

种特训方案" 可知，我们最重要添加一些边，使得形成一棵树，这意味着图中不能有环，初始的结构一定是森林。我们可以通过 dfs 判环，如果有环，则无解。

因此，在初始每棵树的内部，两两节点之间的最短距离是唯一的，可通过预处理直接求出。我们需要找出到达其他节点距离之和最小的点，用于连接不同的连通块，这个点就是树的重心。添加新边时，把每个连通块看成一个节点。问题转化为构造一棵新树，使其每条经过次数与权值乘积之和最小。贪心地考虑，我们要让权值最小的边经过次数最多，且最短路径长度之和尽可能少，一定要构造菊花图，让权值最大的连通块作为根节点，其他的作为叶节点。我们把所有边按边权从大到小排序，边权最小的边连接最大连通块，边权次小的边连接次大连通块，以此类推。

贪心的证明如下：

设连通块的数量为 $k$ ，大小分别为 $siz_1,siz_2,...,siz_k$ ，不妨设 $siz_1 \geq siz_2 \geq ...\geq siz_k$ ；
已知某条边 $i$ 与连通块 $p_i$ 相连,则该条边对答案贡献 $q_i \geq siz_{p_i} (n-siz_{p_i})a_i$ ；
令 $c_i=siz_i (n-siz_i)$ ,则 $c_1 \geq c_2 \geq ... \geq c_k$ ；
令 $S_i=\sum\limits_{i=1}^kc_{p_i}$ ， $s_i=\sum\limits_{i=1}^k c_{i}$ ，构造 $d_{1,i}=a_j (S_{j-1} < i \le S_{j})$ ， $d_{2,i}=a_j (s_{j-1} < i \le s_{j})$ ，则 $\sum d_{1,i} =\sum\limits_{i=1}^k c_{p_i}a_i$ , $\sum d_{2,i} =\sum\limits_{i=1}^k c_ia_i$ . 由 $s_j \le S_j$ 可知 $d_{1,i} \geq d_{2,i}$ ,于是 $\sum d_{1,i} \geq \sum d_{2,i}$ ，即 $\sum\limits_{i=1}^k c_{p_i}a_i \geq \sum\limits_{i=1}^k c_ia_i$ ；
总答案 $\sum\limits_{i=1}^k q_i \geq \sum\limits_{i=1}^k c_{p_i}a_i \geq \sum\limits_{i=1}^k c_ia_i$
依照上述方法构造菊花图，则 $\sum\limits_{i=1}^k q_i = \sum\limits_{i=1}^k c_ia_i$ ，得证。

题解：P12007 【MX-X10-T3】[LSOT-4] 全国联赛？

文章操作

相关推荐

评论

题解：P12007 【MX-X10-T3】[LSOT-4] 全国联赛？