ToB企服应用市场:ToB评测及商务社交产业平台

标题: VK Cup 2017 Round 3 - D. Perishable Roads（最短路：将问题性质挖掘到极 [打印本页]

作者: 魏晓东 时间: 2022-8-13 05:29
标题: VK Cup 2017 Round 3 - D. Perishable Roads（最短路：将问题性质挖掘到极
VK Cup 2017 - Round 3 - D. Perishable Roads

题目链接：

传送门: https://codeforces.com/contest/773/problem/D
题目大意：

对于每一个点\(i\in[1,n]\)，求解以点\(i\)为根的生成树使得\(ans_i=\sum_{j=1}^nd(j)\)最小，其中\(d(j)\)为结点\(j\)到根\(i\)路径上的最小边权。输出\(ans_i\)。
解题思路：

在简单的题意下藏着许多有待挖掘的性质。
性质1：以点\(i\)为根的生成树一定是一条路径；
设\(w_j\)表示路径上第\(j\)条边的权，\(ans_i=\sum_{j=1}^nd(j)=\sum_{j=1}^{n-1}\min_{l=1}^jw_l\);
这个时候我们已经可以以每一个点为根使用复杂度为\(O(n^2)\)的最短路算法；
性质2：路径上一定包括权最小的某一条边；
令所有边减去最小边权\(v\)，在计算\(ans\)时，加上\(（n-1)\times v\)。我们发现当路径经过权值为0的边后，之后路径上所经过的每一个点对￥的贡献都是0；
因此我们可以考虑，以端点\(x\)为源点（\(x\)为若干条权最小的边关联的若干端点），倒推每一个点为根的路径；
性质3：设最优路径为\(w_1,w_2,...,w_k,...,w_n-1\)，\(k\)表示最小边权在路径上的位置。则一定有\(iw_{i+1}\)；
我们简要证明一下性质3；

反证：设存在\(i

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)