题意：

N个点。N行N列d[i][j]。

d[i][j]：结点i到结点j的距离。

问这N个点是否可能是一棵树。是输出YES，否则输出NO。

思路：

假设这个完全图是由一棵树得来的，则我们对这个完全图求最小生成树，得到原树。（画个图就明白）

故我们对完全图求最小生成树，然后用DFS从这棵树上的每个点出发，判断距离是否和矩阵d相同。

注意：

用vector存与每个点相连树枝的另一端，否则超时。用了vector也耗了1400多秒，限时2s。

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include

bool cmp(node a,node b){
return a.len<b.len;
}

int findFa(int x){
if(fa[x]!=x) fa[x]=findFa(fa[x]);
return fa[x];
}

bool dfs(int start,int x,int fa,int weight){
if(d[start][x]!=weight){
return false;
}
int L=graph[x].size();
rep(i,0,L-1){
int v=graph[x][i];
if(v==fa) continue;
bool t=dfs(start,v,x,weight+a[x][v]);
if(!t) return false;
}
return true;
}

int main(){
scanf("%d",&n);
rep(i,1,n) rep(j,1,n) scanf("%d",&d[i][j]);

rep(i,1,n) if(d\[i\]\[i\]!=0){  
    printf("NO\\n");  
    return 0;  
}  
rep(i,1,n-1) rep(j,i+1,n){  
    if(d\[i\]\[j\]==0 || (d\[i\]\[j\]!=d\[j\]\[i\])){  
        printf("NO\\n");  
        return 0;  
    }  
}

int eNum=0;  
mem(a,0);

rep(i,1,n-1) rep(j,i+1,n){  
    edge\[++eNum\].x=i, edge\[eNum\].y=j;  
    edge\[eNum\].len=d\[i\]\[j\];  
}  
sort(edge+1,edge+1+eNum,cmp);  
rep(i,1,n) fa\[i\]=i;  
rep(i,1,n) graph\[i\].clear();

rep(i,1,eNum){  
    int xx=edge\[i\].x, yy=edge\[i\].y;  
    int fx=findFa(xx), fy=findFa(yy);  
    if(fx!=fy){  
        fa\[fx\]=fy;  
        a\[xx\]\[yy\]=a\[yy\]\[xx\]=edge\[i\].len;  
        graph\[xx\].push\_back(yy);  
        graph\[yy\].push\_back(xx);  
    }  
}

int t=findFa(1);  
rep(i,2,n) if(findFa(i)!=t){  
    printf("NO\\n");  
    return 0;  
}

rep(i,1,n){  
    bool k=dfs(i,i,-1,0); //从顶点i出发  
    if(!k){  
        printf("NO\\n");  
        return 0;  
    }  
}  
printf("YES\\n");  

}