树的重量，洛谷之提高历练地，较复杂图论I

正题

      第二题：树的重量

      没错这题代码很短。。。

      我们先考虑两个点的连边，很明显就是随意的，因为两个点之间的连线始终都是要算上去的。

      所以我们先假设先选1，2.

      然后我们加入3，这个点，那么他分支出来的距离也是很好求出来的。

当前1到2的距离是y，1到3的距离是z，2到3的距离是q，我们如果可以求得x，那么树的重量要增加的值也可以求出来了。

学过容斥原理的就知道z+q-2*x=y.没学过的也知道

解一下方程就可以知道x=(z+q-y)/2;

我们要求这个东西最小，对应到原来的dis数组可以知道x=(dis[i][k]+dis[j][k]-dis[i][j])/2;

所以如果我们可以知道最小的i和j的话，就可以算出要加上的值了。噢噢噢噢？？正解TLE？？

还差一点，因为dis[i][k]+dis[j][k]-dis[i][j]同等于dis[1][j]+dis[j][k]-dis[1][j]。。为什么？因为解这个方程算出来的值都是一样的，所以可以不用理。

#include<cstdio>
#include<cstdlib>
#include<cstring>

int n;
int d[35][35];

int main(){
	while(scanf("%d",&n)){
		if(n==0) break;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				int x;
				scanf("%d",&x);
				d[i][j]=d[j][i]=x;
			}
		}
		int tot=d[1][2];
		for(int i=3;i<=n;i++){
			int mmin=1e9;
			for(int j=1;j<=i-2;j++)
				for(int k=j+1;k<=i-1;k++){
					if((d[i][j]+d[i][k]-d[j][k])/2<mmin) mmin=(d[i][j]+d[i][k]-d[j][k])/2;
				}
			tot+=mmin;
		}	
		printf("%d\n",tot);
	}
}