题解 P1268 【树的重量】

查看原题请戳这里

一个非常直观的思路是直接通过搜索得到树的形态以及每一条边的边权，但是这样做貌似非常慢，所以我们可以换一种思路。

我们可以发现，因为题目让求的是树的边权的和，所以我们其实不用太关心最终树的形态。

我们从易到难进行考虑：

当只有$2$个点时，树应该是这样的：

抽象一下：

很显然，$ans=dis(1,2)$。

那么，如果有$3$个点呢？

考虑到如果想让最终的总边权最小，而点与点之间的距离又不变，那么我们应该尽量选取最长的公共边，于是我们可以$1->2$这条链上插入$3$.

如图，其中红边边权$k$为我们插入节点$3$所消耗的最小代价，其中$k=(dis(1,3)+dis(2,3)-dis(1,2))/2$(总距离-公共边的距离)

然后我们再考虑第$4$给点：

如图，红边和蓝边代表着节点$4$不同的插入位置，即选择了不同的边为公共边。

如果有更多的点，我们应该枚举其插入的位置，取最小值并更新答案。

特殊的，我们初始选择了$1->2$这条边，所以要把$dis(1,2)$加入答案。

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n,ans,map[105][105];

int main()
{
    n = read();
    while(n)
    {
        for(re int i = 1; i <= n; i++)
            for(re int j = i + 1; j <= n; j++)
                map[i][j] = map[j][i] = read();
        ans = map[1][2];
        for(re int i = 3; i <= n; i++)
        {
            int Min = INF;
            for(re int j = 1; j <= i - 1; j++)
                for(re int k = j + 1; k <= i - 1; k++)
                    Min = min(Min,map[i][j] + map[i][k] - map[j][k]);
            ans = ans + (Min >> 1);
        }
        printf("%d\n",ans);
        n = read();
    }
    return 0;
}