链接：https://ac.nowcoder.com/acm/contest/3007/I
来源：牛客网

题目描述

小 Q 所在的国家有 N 个城市，城市间由 N-1 条双向道路连接，任意一对城市都是互通的。
每条道路有一个长度，自然，小 Q 的导航系统能显示每对城市间的最短距离。
但是小 Q 对这个系统并不太放心，于是他向你求助：
给定每对城市间的最短距离，你要判断距离表是否一定有误。
如果这张距离表是自洽的，那么请你按升序依次给出每条道路的长度。
对于全部的数据，1≤N≤500，输入的所有数字都是不超过 10 9 的非负整数。

输入描述:

第一行一个数字 N
接下来 N 行，每行 N 个正整数
第 i 行第 j 列的数字表示城市 i 和城市 j 间的最短距离
保证第 i 行第 i 列的数字为 0

输出描述:

第一行，一个字符串
如果距离表没有问题，输出“Yes”
并在接下来的 N-1 行从小到大给出每条道路的长度
否则输出“No”即可
示例1

输入

复制 
3
0 1 2
1 0 1
2 1 0

输出

复制 
Yes
1
1
示例2

输入

复制 
3
0 1 1
1 0 1
1 1 0

输出

复制 
No

题解　

　　　跑一遍MST得出道路长度长，跑一遍Floyd处理出任意两点间距离并与导航给出的距离对比

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 507;
 47 
 48 struct node
 49 {
 50     int u,v,w;
 51 }e[maxn*maxn];
 52 
 53 int fa[maxn];
 54 LL g[maxn][maxn];
 55 LL dis[maxn][maxn];
 56 
 57 int tot[maxn];
 58 
 59 int fid(int x)
 60 {
 61     return fa[x]==x ? x : fa[x] = fid(fa[x]);
 62 }
 63 
 64 bool cmp(node a,node b)
 65 {
 66     return a.w < b.w;
 67 }
 68 
 69 int main()
 70 {
 71     int n;
 72     int num=0,x,sum=0;
 73     read(n);
 74     for(int i = 1; i <= n; ++i) {
 75         for(int j = 1; j <= n; ++j) {
 76              read(x);
 77              g[i][j] = x;
 78              if(i != j)
 79              {
 80                 e[++num].w=x;
 81                 e[num].u=i;
 82                 e[num].v=j;
 83              }
 84         }
 85     }
 86     sort(e+1,e+num+1,cmp);
 87     for(int i = 1; i <= n; ++i) {
 88         for(int j = 1; j <= n; ++j) {
 89             if(i == j) dis[i][j] = 0;
 90             else dis[i][j] = 1e18;
 91         }
 92     }
 93     for(int i = 1; i <= n; ++i) {
 94         fa[i] = i;
 95     }
 96     int u,v;
 97     for(int i = 1;i <= num; ++i) {
 98         u = e[i].u;
 99         v = e[i].v;
100         if(fid(u)!=fid(v))
101         {
102             dis[u][v] = dis[v][u] = e[i].w;
103             tot[++sum] = e[i].w;
104             fa[fa[u]] = fa[v];
105         }
106     }
107     for(int k = 1; k <= n; ++k) {
108         for(int i = 1; i <= n; ++i) {
109             for(int j = 1; j <= n; ++j) {
110                 dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
111             }
112         }
113     }
114     for(int i = 1; i <= n; ++i) {
115         for(int j = 1; j <= n; ++j) {
116              if(dis[i][j] != g[i][j]) {
117                 printf("No");
118                 return 0;
119              }
120         }
121     }
122     printf("Yes\n");
123     sort(tot+1,tot+n);
124     for(int i = 1; i < n; ++i) {
125         printf("%d\n",tot[i]);
126     }
127 }
View Code