题意：给出一个距离矩阵，问是不是一颗正确的带权树。
解法：先按找距离矩阵建一颗最小生成树，因为给出的距离都是最短的点间距离，然后再对每个点跑dfs得出应该的dis[][]，再对比dis和原来的mp是否一致即可。
首先还要判断一些东西。具体看代码吧。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define N 2007 struct Edge
{
int u,v,w;
}edge[N*N];
int a[N][N],fa[N],dis[N][N];
vector<pair<int,int> > G[N];
int cmp(Edge ka,Edge kb) { return ka.w < kb.w; }
int findset(int x)
{
if(x != fa[x])
fa[x] = findset(fa[x]);
return fa[x];
} void dfs(int u,int fa,int ori)
{
for(int i=;i<G[u].size();i++)
{
int v = G[u][i].first;
if(v == fa) continue;
dis[ori][v] = dis[ori][u] + G[u][i].second;
dfs(v,u,ori);
}
} int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%I64d",&a[i][j]);
int tag = ;
for(i=;i<=n;i++)
{
fa[i] = i;
for(j=;j<=n;j++)
{
if((i == j && a[i][j] != )||(i != j && a[i][j] == )||(a[i][j] != a[j][i]))
{
tag = ;
break;
}
}
if(!tag) break;
}
if(!tag) { puts("NO"); continue; }
int tot = ;
for(i=;i<=n;i++)
for(j=i+;j<=n;j++)
edge[tot].u = i, edge[tot].v = j,edge[tot++].w = a[i][j];
sort(edge,edge+tot,cmp);
for(i=;i<tot;i++)
{
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
int fx = findset(u), fy = findset(v);
if(fx != fy)
{
G[u].push_back(make_pair(v,w));
G[v].push_back(make_pair(u,w));
fa[fx] = fy;
}
}
for(i=;i<=n;i++)
{
dis[i][i] = ;
dfs(i,,i);
for(j=;j<=n;j++)
{
if(a[i][j] != dis[i][j])
{
tag = ;
break;
}
}
if(!tag) break;
}
if(!tag)
puts("NO");
else
puts("YES");
}
return ;
}