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\)表示最小边权在路径上的位置。则一定有\(i<=k-3\)时，\(w_i>w_{i+1}\)；

我们简要证明一下性质3；

反证：设存在\(i<=k-3\)时，\(w_i\leq w_{i+1}\)，那么第\(i+1\)条边的实际贡献至多为\(w_i\)，而我们可以通过至多\(w_i\)的花费直接到达源点\(x\)，而不需要通过原来的第\(i+1\)条边，显然这样更优，因此原假设不成立；

因此，最多只存在\(w_{k-1}<w_k\)这一特殊情况，可以理解成，路径边权最小值变为\(w_{k-1}\)后，无法进一步优化，故而选择边权为\(w_k\)的边直接到达源点\(x\)；这个情况对应的权值和是\(2w_{k-1}\)，我们将其作为最短路数组的初始值。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 LLL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef pair<double,double> pdd;
typedef complex<double> comp;
const int N=2e3+5;
const int M=605;
const int inf=0x3f3f3f3f;
const LL mod=998244353;
const double eps=1e-9;
const double pi=acos(-1.0);
const int S=100;
#define ls (i<<1)
#define rs (i<<1|1)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))

inline LL read()
{
    LL x=0,t=1;
    char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') t=-1;
    while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); }
    return x*t;
}
LL dis[N];
int a[N][N],vis[N];
int main()
{
    int n,v=inf;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            scanf("%d",&a[i][j]);
            a[j][i]=a[i][j];
            v=min(a[i][j],v);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j) a[i][j]-=v;
        }
    }
    mem(dis,0x3f);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j) dis[i]=min(dis[i],1LL*a[i][j]<<1);
    for(int i=1;i<n;i++){
        int pos=0;
        for(int j=1;j<=n;j++){
            if(vis[j]) continue;
            if(!pos||dis[pos]>dis[j]) pos=j;
        }
        vis[pos]=1;
        for(int j=1;j<=n;j++){
            if(vis[j]) continue;
            dis[j]=min(dis[j],dis[pos]+a[pos][j]);
        }
    }
    for(int i=1;i<=n;i++) printf("%lld\n",dis[i]+1LL*(n-1)*v);
    return 0;
}