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

而每个节点都可以从 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 ; }