Codeforces 472D-白红宇

Codeforces 472D

阅读量：7108 次

发布时间：2019-06-28

本文共 718 字，大约阅读时间需要 2 分钟。

看官方题解提供的是最小生成树，怎么也想不明确。you can guess and prove it！

看了好几个人的代码。感觉实现思路全都不一样，不得不佩服cf题目想法的多样性

以下说说我自己的理解，将1作为根，对于随意两点存在两种关系：

1.一个点位于还有一个点的子树上。两点到1的距离之差绝对值等于两点距离。

2.两个点在某一个点的不同子树上。两点到1距离之和减去两点距离等于两倍某个点到1的距离。

这样不须要管父节点是哪一个，仅仅要保证存在即可了。

推断这两种情况就能够了。

当然在開始的时候要注意一些特殊情况的推断，预处理一下。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             using namespace std;int n;long long mp[2005][2005];map 
              
                m;int main(){ int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%I64d",&mp[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if((i==j && mp[i][j]) || (i!=j && mp[i][j]==0) || mp[i][j]!=mp[j][i]) { cout<<"NO"<