luogu p1268 树的重量——构造，真正考验编程能力

题目链接：http://www.luogu.org/problem/show?pid=1268#sub

---

---

解决所有“构造”问题都要按照如下的步骤：

1. 寻找特例、特征
2. 建立模型
3. 一般化模型

• 寻找特例
  
  (1) 我们假设结点数为1，显然答案为0，因为这棵树的边集为空。
  
  (2) 当结点数为2时，答案就是d[1][2]，即(1,2)的距离。
  
  (3) 当结点数为3时呢？明显(1,3)和(2,3)这两条边有重叠的部分，那重叠的部分是几呢？
  
  
  
  如图所示，(1,3)和(2,3)的重叠部分，记作l，其值为$(8+9-5)/2=6。

• 建立模型
  
  还是结点数为3的情况，这次把d[1][2],d[1][3],d[2][3]分别设为x,y,z，那么(1,3)和(1,2)的“重叠”部分就应该是\((y+z-x)/2\)

• 一般化模型
  
  如果结点数为四呢？
  
  

如图，只要求出红色的部分就可以了。

至于红色的部分怎么求，详细请见代码，在这里[^http://blog.sina.com.cn/s/blog_610128b00100dsic.html]解释得很详细了

//自己选择的路就算跪着也要走完 系列

//题目：P1268

#include <iostream>

#include <cstring>

using namespace std;

const int maxn=35;

int n,a[maxn][maxn]={0};

int main(){

	while (cin>>n,n!=0){

		memset(a,0,sizeof(a));

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

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

				cin>>a[i][j],a[j][i]=a[i][j];

		int ans=a[1][2];

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

			int min=0x3f3f3f3f;

			for (int j=2;j<i;j++){

				int x=a[1][j],y=a[1][i],z=a[i][j],xyz=(y+z-x)/2;

				min=min>xyz?xyz:min;

			}

			ans+=min;

		}

		cout<<ans<<endl;

	}

	return 0;

}