CF773D Perishable Roads

题目描述：

有一个 \(n\) 个点的图，对于每两个点 \((i,j)\) 之间都有一条长度为 \(w_{i,j}\) 的无向边。

给你一个点 \(t\)，你需要构造一棵以 \(t\) 为根的生成树，使得\(\sum\limits_{i=1}^{n}s(i,t)\) 尽量小。\(s(i,t)\) 为 \(i\rightarrow t\) 的树上路径上的最小权值。

你需要对于每个 \(t\) 都求出答案。

数据范围：

\(n\le 2000\)

\(1\le w_i\le 10^9\)

思路：

首先我们手摸一下样例，显然我们希望尽可能使得整体的距离最小，则需要满足尽可能多的点都是经过最短边然后到达 \(t\)。

在进行正式的讲解之前，我们先进行一些定义：

1. \(mn\) 表示最小的边长，\(st\) 表示最小的边连接的点

所以我们就可以将整个图分为两个部分：

1. \(st\Rightarrow t\) 的这条链
2. 以 \(st\) 为根且到 \(t\) 最小值为 \(mn\) 的一棵树

注意：最小边在树和链的连接处

然后我们分别考虑怎么计算这个两个部分。

对于链的部分，我们不难发现一个性质：必定存在一种最优方案，使得从st到t的这条链上边权单调不降

这个性质的证明也是比较简单的。

我们考虑反证法：如果有一条递减的边，则把这个点放到链起点的位置显然不会更劣。所以问题就转换为求一条最短路径的长度

所以我们以 \(st\) 为起点跑一边最短路，就可以得到以 \(i\) 为终点的链上的最小代价。

然后我们考虑如何计算树的部分的答案：

令整条路径上经过的点的数量为 \(x\)，则一共 \(n-x\) 个在树上的点（这里的树不是整棵生成树）然后贡献就是 \((n-x)\times mn\)

然后我们发现这个东西不是很好计算，所以我们不妨对原式进行一些修改（这个改动我根本没想到）

将 \(x\) 的定义变为链上的边的数量，则贡献变为 \((n-x-1)\times mn\to (n-1)\times mn-x\times mn\)

所以我们不妨对于原图中的每一条边都减去 \(mn\)。

这样最后的答案就可以转变为 \(dis_t+(n-1)\times mn\)

后记：

关于一些疑问：

1. 为什么只需要进行一个 \(mn\) 两端的点就可以了？

仔细观察代码，我们在代码中有这样的几行

for(int j=1;j<=n;j++)if(j!=i)dis[i]=min(dis[i],g[j][i]*2);

所以我们不难发现，这个东西实际上包含了另外一种情况，具体的可以画图理解一些：

对于这个图，显然 \(st=1\)

这个涉及到在处理的时候与 \(st\) 连边的有哪些点？

1. 直接连边
2. 经过一个转折点

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2005;
const int inf=1e18;
int n;
int g[maxn][maxn];
int mn=inf,st;
int vis[maxn],dis[maxn];
void Dijkstra(int st){
    for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
    vis[st]=1;
    for(int i=1;i<=n;i++){
        dis[i]=g[st][i];
        for(int j=1;j<=n;j++)if(j!=i)dis[i]=min(dis[i],g[j][i]*2);
    }
    for(int i=1;i<n;i++){
        int u=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&(u==-1||dis[j]<dis[u]))u=j;
        }
        vis[u]=1;
        for(int v=1;v<=n;v++){
            dis[v]=min(dis[v],dis[u]+g[u][v]);
        }
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            scanf("%lld",&g[i][j]);
            g[j][i]=g[i][j];
            if(mn>g[i][j]){
                mn=g[i][j];
                st=i;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            g[i][j]-=mn;
            g[j][i]-=mn;
        }
    }
    Dijkstra(st);
    for(int i=1;i<=n;i++){
        printf("%lld\n",dis[i]+mn*(n-1));
    }
    return 0;
}

可能讲的有些凌乱，还请多多海涵