P1268 树的重量 【数学】

· · 题解

算是一种贪心吧

当n=2时，显然答案就是dis(1,2)。

当n=3时，（下图是偷来的）（水印还是洛谷2.0呢……）

答案是dis(1,2)+蓝线长度

蓝线长度是\frac {dis(1,3)+dis(2,3)-dis(1,2)}{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}} 
#include<bits/stdc++.h>
using namespace std;
int n,dis[35][35];
int main()
{
    while(~scanf("%d",&n))
    {
        if(!n) break; 
        for(int i=1;i<n;i++)
            for(int j=i+1;j<=n;j++)
                scanf("%d",&dis[i][j]);
        int ans=dis[1][2];
        for(int i=3;i<=n;i++)
        {
            int tmp=0x7fffffff;
            for(int j=2;j<i;j++) 
                tmp=min(tmp,(dis[1][i]-dis[1][j]+dis[j][i])/2);
            ans+=tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}