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

· · 题解

感觉此题可以评蓝。

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

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

贪心的证明如下：

  1. 设连通块的数量为 k ，大小分别为 siz_1,siz_2,...,siz_k，不妨设 siz_1 \geq siz_2 \geq ...\geq siz_k ；
  2. 已知某条边 i 与连通块 p_i 相连,则该条边对答案贡献 q_i \geq siz_{p_i} (n-siz_{p_i})a_i ；
  3. 令 c_i=siz_i (n-siz_i) ,则 c_1 \geq c_2 \geq ... \geq c_k ；
  4. 令 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；
  5. 总答案 \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
  6. 依照上述方法构造菊花图，则 \sum\limits_{i=1}^k q_i = \sum\limits_{i=1}^k c_ia_i ，得证。