題意：給定一個矩陣，表示每兩個節點之間的權值距離，問是否可以對應生成一棵樹，
使得這棵樹中的任意兩點之間的距離和矩陣中的對應兩點的距離相等！
思路：我們將給定的矩陣看成是一個圖，a 到 b會有多條路徑， 如果存在一棵樹，那么
這個樹中a->b的距離一定是這個圖中所有a->b中路徑長度最短的一條！所以我們根據邊權，
建立一棵MST樹！再將MST樹中的任意兩點之間的距離求出來，看是否和矩陣中的對應的節點
對距離相同！
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){//求最小生成樹中任意兩個節點的距離 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 }
?
..doc)
)
)
)
