首页 > 代码库 > POJ2485 最小生成树

POJ2485 最小生成树

2024-07-10 14:50:57   229人阅读

问题：POJ2485

本题求解生成树最大边的最小值

分析：

首先证明生成树最大边的最小值即最小生成树的最大边。

假设：生成树最大边的最小值比最小生成树的最大边更小。

不妨设C为G的一个最小生成树，e是其中的最大边。把e从C中去除，则C被分成C1，C2两个连通子集。假设存在最大边小于e的生成树CC，则CC中连接C1，C2两个点集的桥ee必定小于e。把C中的e换成ee，则 C1,C2,ee必定也生成一个生成树。该生成树长度小于C，与C是最小生成树的事实矛盾，故假设不成立。

因此必有：

生成树最大边的最小值 = 最小生成树的最大边。

故本题转化为求解已知图的最小生成树，用PRIM法即可。

AC代码：
 1 //Memory: 532K        Time: 172MS 2 #include <iostream> 3 #include <cstring> 4 #include <string> 5 #include <algorithm> 6  7 const int maxn = 501; 8 int g[maxn][maxn]; 9 bool vis[maxn];10 int d[maxn];11 int n, t; 12 int _min, _max;13 14 void prim()15 {16     memset(vis, 0, sizeof(vis));17     vis[0] = 1;18     int size = 1;19     _max = 0;20     for (int i = 1 ; i < n; i++){21         d[i] = g[0][i];22     }23     while (size < n) {24         _min = 65536;25         int k;26         for (int i = 1; i < n; i++) {27             if ( !vis[i] && d[i] < _min) {28                 _min = d[i];29                 k = i;30             }31         } 32         vis[k] = 1;33         if (_min > _max) _max = _min;34 35         for (int i = 0; i < n; i++) {36             if ( !vis[i] && g[i][k] < d[i])37                 d[i] = g[k][i];38         }39         size++;40     }41 }42 43 int main()44 {45     scanf("%d", &t);46     while (t--){47         scanf("%d", &n);48         for (int i = 0; i < n; i++)49             for (int j = 0; j < n; j++)50                 scanf("%d", &g[i][j]);51         prim();52         printf("%d\n", _max);53     }54     return 0;55 }

 


联系
我们