Luogu P1268 树的重量

当\(n=2\)时，显然\(ans=dis(1,2)\).
当\(n=3\)时，路径总和为\(dis(1,2)\)加上点\(3\)到点\(1\)点\(2\)连线的长度。即\(ans=dis(1,2)+\frac{dis(1,3)+dis(2,3)-dis(1,2)}{2}\).
那么考虑\(n\)为任意值时，第\(n\)条路径可以处于点\(1\)到点\(2\)~\((n-1)\)的任意一条路径上产生分支，那么我们显然要找最小值，因此可得\[ans=dis(1,2)+\sum_{i=3}^{n}(min_{j=2}^{i-1}\frac{dis(1,i)+dis(i,j)-dis(1,j)}{2})\]
但是，这道题最坑的不在于此：
因为其神奇的读入方式，我们的\(dis(i,j)\)是不等于\(dis(j,i)\)的。
这个时候，你如果直接套上面那个公式，就会错掉。
有两种处理方法：
1.在读入时初始化一下。

for(int i=1;i<=n-1;i++) {
    for(int j=i+1;j<=n;j++) {
        scanf("%d",&dis[i][j]);
        dis[j][i]=dis[i][j];
    }
}

2.因为读入的\(dis(i,j)\)都是\(i<j\)的，所以公式中把\(dis(i,j)\)换为\(dis(j,i)\)即可。

for(int i=3;i<=n;i++) {
    tmp=INF;
    for(int j=2;j<=i-1;j++) {
        tmp=min(tmp,(dis[1][i]+dis[j][i]-dis[1][j])/2);
    }
    ans+=tmp;
}

完整代码：

#include<bits/stdc++.h>
#define INF 0x7fffffff

using namespace std;

int n,ans,tmp;
int dis[40][40];


int main()
{
    while(scanf("%d",&n)) {
        if(n==0) {
            return 0;
        }
        for(int i=1;i<=n-1;i++) {
            for(int j=i+1;j<=n;j++) {
                scanf("%d",&dis[i][j]);
                dis[j][i]=dis[i][j];
            }
        }
        ans=dis[1][2];
        for(int i=3;i<=n;i++) {
            tmp=INF;
            for(int j=2;j<=i-1;j++) {
                tmp=min(tmp,(dis[1][i]+dis[i][j]-dis[1][j])/2);
            }
            ans+=tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Luogu P1268 树的重量

原文：https://www.cnblogs.com/luoshui-tianyi/p/11520972.html