洛谷P1268 树的重量

因为所有的节点都是叶节点,因此每个叶节点都是从已有的节点中分出来的

而每个节点都可以从 1 ~ j (j < i ) 中分出 (当然类似于floyd三层循环枚举也可以)

设i为要插入的节点 , j为dis[1][j] 中最小的那个(j<i)

minn = min ( (dis[1][i]+dis[j][i] - dis[1][j])/2 ) ;

floyd的话是

for ( int i = 3;i <= n; ++i ) {
            int minn = 999999999 ;
            for ( int j = 1; j <= i - 1; ++j )
              for ( int k = 1; k <= j - 1; ++k ) {
                 minn = min ( minn, ( dis[j][i] + dis[k][i] - dis[j][k] ) / 2 );
           }
           ans += minn;
      }

其中i为要插入的节点,j为枚举的起点1,k位枚举的起点2,jk就是要分的线段

code

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 100
using namespace std ;
int n , a[maxn][maxn] , ans , minn ;
int main () {
	while(cin >> n ) {
		if(n == 0) return  0 ;
 		ans = 0 ;
		for(int i = 1 ; i < n ; i ++) {
			for(int j = i + 1 ; j  <= n ; j ++) {
				cin >> a[i][j] ;
			}
		}
		ans = a[1][2] ;
		for(int i = 3 ; i <= n ; i ++) {
			int minn = 999999 ;
			for(int j = 2 ; j < i ; j ++) {
				minn = min(minn,(a[1][i]+a[j][i]-a[1][j])/2) ;
			}
			ans += minn ;
		}
		cout << ans << endl ;
	}
	return 0 ;
}