首页 > 代码库 > Codeforces 472(#270 ) D Design Tutorial: Inverse the Problem

Codeforces 472(#270 ) D Design Tutorial: Inverse the Problem

2024-07-25 10:11:39   219人阅读

题意：给你一棵数的距离矩阵，问你这个矩阵是否合法

解题思路：利用树的性质进行prime 和连边，产生最小生成树，最后看最小生成树是否和给出的一致就行

解题代码：

  1 // File Name: d.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月29日 星期一 00时45分45秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 2010 26 using namespace std; 27 int n ;  28 int mi[maxn]; 29 vector <int> mp[2010]; 30 int nmp[maxn][maxn]; 31 int pre[maxn]; 32 bool vis[maxn]; 33  34 long long  dep[maxn]; 35 void dfs(int la,int zla,int dis) 36 { 37    dep[la] = dis;    38    int len = mp[la].size(); 39    for(int i = 0 ;i < len ;i ++) 40    { 41        int ne = mp[la][i]; 42        if(ne != zla) 43        { 44           dfs(ne,la,dis + nmp[la][ne]); 45        } 46    } 47 } 48 void prime() 49 { 50     for(int i = 1;i <= n;i ++){ 51        dep[i] = 2e9; 52        vis[i] = 0 ;  53     }         54     dep[1] = 0 ;  55     while(1) 56     { 57        int v = -1; 58        for(int i = 1;i <= n;i ++) 59        { 60           if(!vis[i] && (v == -1 || dep[i] < dep[v])) 61               v = i ;   62        } 63        if(v == -1) 64            break; 65        vis[v] = 1; 66        for(int i = 1;i <= n;i ++) 67        { 68            if(!vis[i] && nmp[v][i] < dep[i])  69            { 70               dep[i] = nmp[pre[i] = v][i]; 71            } 72        } 73     } 74 } 75 int main(){ 76      scanf("%d",&n); 77      int sum = 0 ;  78      int ok  = 0 ; 79      for(int i = 1;i <= n;i ++) 80      {  81         for(int j = 1;j <= n;j ++) 82         { 83             scanf("%d",&nmp[i][j]); 84         } 85      } 86      for(int i = 1;i <= n;i ++) 87      { 88         for(int j = 1;j <= n;j ++) 89         { 90            if(i!= j && nmp[i][j] == 0 ) 91                ok = 1; 92            if(nmp[i][j] != nmp[j][i]) 93                ok = 1; 94         } 95      } 96      if(ok) 97      { 98        puts("NO"); 99        return 0 ; 100      }101      prime();102      for(int i = 2;i <= n;i ++)103      {104        mp[i].push_back(pre[i]);105        mp[pre[i]].push_back(i);106        //printf("%d %d\n",i,pre[i]);107      }108      for(int i = 1;i <= n;i ++)109      {110         dfs(i,0,0);111     /*    for(int j = 1;j <= n;j ++)112             printf("%lld ",dep[j]);113         printf("\n");*/114         for(int j = 1; j <= n;j ++)115         {116            if(dep[j] != nmp[i][j])117            {118               119               puts("NO");120               return 0;121            }122         }123      }124      puts("YES");125 return 0;126 }
View Code

 

Codeforces 472(#270 ) D Design Tutorial: Inverse the Problem


联系
我们