Problem A: 道路建设解题报告

程序员篷骏技术 2022年11月16日

0 收藏 741 点赞 2,913 浏览 918 个字

一定存在一个最优解是一条链

否则可以接上去，不会更差
边权最小的边一定在这条链上

这个比较显然

可以把所有边都减去这个最后加上就行了
把链上的边按距离当前根的深度从小到大排列，设第一个零边位置为$k$，那么到$k-2$及之前所有的边边权非严格递减，这个可以手玩一下。

具体思路就是如果不递减，就可以强行把0边一个端点接过来，换掉$k-1$，可以证明这样不会变差。

于是边权可以直接累加起来了。
建议一个虚点，连接所有的点，边权为被连接点出边最小边权的两倍。

两倍是模拟把0边拉过来耗掉的那条边，然后如果拉的恰好是0边，计算的时候也没有影响。

其余边照连，从虚点跑单源最短路即可。
为什么跑出的最短路树边权递增？

特殊点在于先连接的那条最短边，反证一下即可。

Code:

#include <cstdio>
#define ll long long
const int N=2010;
int n,g[N][N];
ll mi=(1ll<<50),dis[N],vis[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            scanf("%d",&g[i][j]);
            mi=mi<g[i][j]?mi:g[i][j];
            g[j][i]=g[i][j];
        }
    for(int i=1;i<=n;i++)
    {
        int id=0;
        for(int j=1;j<=n;j++)
            if(i!=j)
            {
                g[i][j]-=mi;
                if(!id||g[i][j]<g[i][id]) id=j;
            }
        dis[i]=2ll*g[i][id];
    }
    for(int i=1;i<=n;i++)
    {
        int id=0;
        for(int j=1;j<=n;j++) if(!vis[j]&&(!id||dis[j]<dis[id])) id=j;
        vis[id]=1;
        for(int j=1;j<=n;j++) dis[j]=dis[j]<dis[id]+g[id][j]?dis[j]:dis[id]+g[id][j];
    }
    for(int i=1;i<=n;i++) printf("%lld\n",dis[i]+1ll*(n-1)*mi);
    return 0;
}