題意：給定一個矩陣，表示每兩個節(jié)點之間的權值距離，問是否可以對應生成一棵樹，
使得這棵樹中的任意兩點之間的距離和矩陣中的對應兩點的距離相等！
思路：我們將給定的矩陣看成是一個圖，a 到 b會有多條路徑， 如果存在一棵樹，那么
這個樹中a->b的距離一定是這個圖中所有a->b中路徑長度最短的一條！所以我們根據(jù)邊權，
建立一棵MST樹！再將MST樹中的任意兩點之間的距離求出來，看是否和矩陣中的對應的節(jié)點
對距離相同！
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<vector>
5 #include<algorithm>
6 #define N 2005
7 #define M 2000005
8 using namespace std;
9
10 int mp[N][N];
11 int mpp[N][N];
12 int f[N];
13 int vis[N];
14 int n;
15
16 struct node{
17 int v, dist;
18 node(){}
19 node(
int v,
int dist){
20 this->v =
v;
21 this->dist =
dist;
22 }
23 };
24
25 vector<node>
tmp[N];
26
27 struct edge{
28 int x, y, d;
29 edge(
int x,
int y,
int d){
30 this->x =
x;
31 this->y =
y;
32 this->d =
d;
33 }
34 edge(){}
35 };
36
37 int cnt;
38 edge e[M];
39
40 bool cmp(edge a, edge b){
41 return a.d <
b.d;
42 }
43
44 int getFather(
int x){
45 return x == f[x] ? x : f[x] =
getFather(f[x]);
46 }
47
48 bool _union(
int x,
int y){
49 int fx = getFather(x), fy =
getFather(y);
50 if( fx !=
fy){
51 f[fx] =
fy;
52 return true;
53 }
54 return false;
55 }
56
57 void dfs(
int u,
int cur,
int dist){
58 vis[u] =
1;
59 int len =
tmp[u].size();
60 for(
int i =
0; i<len; ++
i){
61 int v =
tmp[u][i].v;
62 if( !
vis[v] ){
63 mpp[cur][v] = mpp[v][cur] = dist+
tmp[u][i].dist;
64 dfs(v, cur, dist+
tmp[u][i].dist);
65 }
66 }
67 }
68
69 int main(){
70 scanf(
"%d", &
n);
71 bool flag =
true;
72 bool flag1 =
false;
73 for(
int i =
1; i <= n; ++
i){
74 f[i] =
i;
75 for(
int j =
1; j <= n; ++
j){
76 scanf(
"%d", &
mp[i][j]);
77 if(j > i) e[cnt++] = edge(i, j, mp[i][j]);
//將邊存起來
78 if(i==j && mp[i][j] !=
0) flag =
false;
//是否自身到自身有權值
79 if( i!=j && !mp[i][j]) flag1 =
true;
//是否都是全零
80 }
81 }
82 if(!flag1 &&
flag){
83 sort(e, e+
cnt, cmp);
84 for(
int i=
0; i<cnt; ++
i)
85 if( _union(e[i].x, e[i].y) )
86 tmp[e[i].x].push_back(node(e[i].y, e[i].d)), tmp[e[i].y].push_back(node(e[i].x, e[i].d));
87
88 for(
int i=
1; flag && i<n; ++i){
//求最小生成樹中任意兩個節(jié)點的距離
89 memset(vis,
0,
sizeof(vis));
90 dfs(i, i,
0);
91 for(
int j=i+
1; flag && j<=n; ++
j)
92 if(!(mp[i][j] == mpp[i][j] && mp[i][j] == mp[j][i]))
//如果最小生成樹中的任意兩點距離和給定的對應的兩點之間的距離不相等
93 flag =
false;
94 }
95
96 if( flag ) printf(
"YES\n");
97 else printf(
"NO\n");
98 }
99 else printf(
"NO\n");
100 return 0;
101 }
View Code ?
轉載于:https://www.cnblogs.com/hujunzheng/p/4001152.html
總結
以上是生活随笔為你收集整理的codeforces D. Design Tutorial: Inverse the Problem的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。
