首页 > 代码库 > Codeforces 472(#270 ) D Design Tutorial: Inverse the Problem
Codeforces 472(#270 ) D Design Tutorial: Inverse the Problem
题意:给你一棵数的距离矩阵,问你这个矩阵是否合法
解题思路:利用树的性质进行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 }
Codeforces 472(#270 ) D Design Tutorial: Inverse the Problem
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。