算法
枚举+构造。
不难发现,$M[i][j]$表示的就是i到j的最短路径。
那么先建一颗$1-2$的树,然后把$3-n$依次加入。
对于第$i$个节点,枚举它之前的所有节点,使所有的非叶子节点尽可能地靠近叶子节点,远离根节点,使公共部分尽量多。
这话有点抽象,我们来具体看看。
画个图就能发现,把节点$i$设为$1-j$路径上分出来的点,则多出来的长度为$(d[1][i]+d[j][i]-d[1][j])/2$。
这个应该很好理解。
那么每次找一个最小的加入就好了。
代码
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
return X*w;
}
int g[50][50];
int main() {
int n;
do {
n=read(); if (n==0) break;
for (re int i=1;i<=n;i++)
for (re int j=i+1;j<=n;j++)
g[i][j]=g[j][i]=read();
int ans=g[1][2];
for (re int i=3;i<=n;i++) {
int now=2147483647;
for (re int j=1;j<i;j++)
now=min(now,(g[1][i]+g[i][j]-g[1][j])/2);
ans+=now;
}
printf("%d\n",ans);
} while (n!=0);
return 0;
}