LuoguP1268树的重量【构造/思维】By cellur925

题目传送门

Description

给你一个矩阵$M$，$M(i,j)$表示$i$到$j$的最短距离。定义树的重量为树上各边权之和，对于任意给出的合法矩阵$M$，已知它所能表示树的重量是唯一确定的。给出一个矩阵，求它所表示的树的重量。

---

Sol

这道题我想了一会发现什么思路都没有...然后企图画一点图也无济于事...

后来看题解发现我们其实可以从简单的角度入手，逐渐发现规律。

当有两个点的时候，显然答案就是$g(1,2)$。

当有三个点的时候，如图，发生了分叉。（因为各点都是叶子节点）

（图片引用自 @TsReaper）

设蓝线部分为$len$，那么树的重量就是$g(1,2)$+$len$。那么$len$部分怎么求？稍微想想可以得出$len=g(1,3)+g(2,3)-g(1,2)$再除以2。

类比一下，当有四个...五个...六个...点的时候，也会在某一个路径上发生分叉，而一个点只可能从在它编号之前的点分叉而来。于是我们对于每个点，枚举一下它是从它之前哪个点分叉过来的，取个最小值累加即可得到答案。

Code

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int n,ans;

 int f[][];

 int main()

 {

     while(scanf("%d",&n)!=EOF&&n)

     {

         for(int i=;i<=n-;i++)

             for(int j=i+;j<=n;j++)

                 scanf("%d",&f[i][j]),f[j][i]=f[i][j];

         ans+=f[][];

         for(int i=;i<=n;i++)

         {

             int tmp=0x3f3f3f3f;

             for(int j=;j<=i-;j++)

                 tmp=min(tmp,(f[][i]-f[][j]+f[i][j])>>);

             ans+=tmp;

         }

         printf("%d\n",ans);

         ans=;

         memset(f,,sizeof(f));

     }

     return ;

 }