题目描述
$ N $ 頂点の重み付き無向木であって、以下の条件を満たすものが存在するか判定して下さい。
- $ 1 \le i \lt j \le N $ を満たす任意の $ 2 $ 整数 $ i,j $ について頂点 $ i $ と頂点 $ j $ の距離が $ A_{i,j} $ である。
ただし、頂点 $ i $ と頂点 $ j $ の距離とは、この $ 2 $ 頂点を結ぶ唯一の単純パスに含まれる辺の重みの総和のことです。
输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ A_{1, 2} $ $ A_{1, 3} $ $ \ldots $ $ A_{1, N} $ $ A_{2, 3} $ $ \ldots $ $ A_{2, N} $ $ \vdots $ $ A_{N-1,N} $
输出格式
条件を満たす木が存在するなら Yes を、存在しないなら No を出力せよ。
输入输出样例 #1
输入 #1
4
2 5 4
3 2
5
输出 #1
Yes
输入输出样例 #2
输入 #2
4
2 5 4
3 2
6
输出 #2
No
输入输出样例 #3
输入 #3
10
1039 1802 3781 231 5828 1944 392 262 1481
763 2742 1270 4789 905 1431 1301 442
1979 2033 5552 142 2194 2064 1205
4012 7531 2121 4173 4043 3184
6059 2175 161 493 1712
5694 6220 6090 5231
2336 2206 1347
654 1873
1743
输出 #3
Yes
说明/提示
Sample Explanation 1
例えば以下の辺をもつ木が条件を満たします。
- 辺 $ (1, 2) $ の重みが $ 2 $
- 辺 $ (2, 3) $ の重みが $ 3 $
- 辺 $ (2, 4) $ の重みが $ 2 $
よって Yes と出力してください。
Sample Explanation 2
条件を満たす木は存在しません。よって No と出力してください。
Constraints
- $ 2 \le N \le 3000 $
- $ 1 \le A_{i,j} \le 9999 $
- 入力される値は全て整数
解法
- 距离可以理解为完全图上的边
- 利用完全图，构造最小生成树，重构新图。
- 验证新图中任意两点的距离是否与原图一致
#include<bits/stdc++.h>
using namespace std;
int n,e[3002][3002],d[3002],v[3002];
vector<int> g[3002];
bool Flg[3002],F;
void dfs(int s,int k) {for (auto x:g[k]) {if (!Flg[x]) {Flg[x]=1;if (e[s][k]+e[k][x]!=e[s][x]) {F=0;return;}dfs(s,x);}}
}int main() {cin>>n;for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++) {int w;cin>>w;e[i][j]=e[j][i]=w;}Flg[1]=1;for (int i=1;i<=n;i++) d[i]=e[1][i],v[i]=1;d[0]=1e9;for (int i=1;i<n;i++) {int k=0;for (int j=1;j<=n;j++)if (!Flg[j] && d[k]>d[j]) k=j;Flg[k]=1;for (int j=1;j<=n;j++)if (!Flg[j] && d[j]>e[k][j]) d[j]=e[k][j],v[j]=k;}for (int i=2;i<=n;i++)g[i].push_back(v[i]),g[v[i]].push_back(i);F=1;for (int i=1;i<=n;i++) {memset(Flg,0,sizeof(Flg));Flg[i]=1;dfs(i,i);if (F==0)break;}if (F) cout<<"Yes\n";else cout<<"No\n";return 0;
}