POJ2485 最小生成树

问题: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 }

POJ2485 最小生成树,布布扣,bubuko.com

时间: 07-05

POJ2485 最小生成树的相关文章

prim最小生成树算法题poj2485

开始想用kruskal算法自己写写runtime error #include<cstdio> #include<queue> #include<set> using namespace std; int a[2510][25100]; struct weight { int a,b; int value; bool operator < (const weight & rhs) const { return value < rhs.value; }

最小生成树prim()算法;

1.最小生成树是指连通所有点的路径之和最小: 2.prim算法是由一个点扩展到所有点,开始生成树中只有一个节点v,第一次扩展,将距离最小生成树最近的节点加入最小生成树,同时更新最小生成树到其他节点的最短路,以此类推,直到所有节点都加入最小生成树. 3.以poj2485为例, 题意:求最小生成树中的最大边长: 源码: #include<iostream>#include<stdio.h>#define MAX 999999using namespace std;int mapp[51

次最小生成树 模版

次小生成树(转) 转载(http://www.cnblogs.com/z360/p/6875488.html) 所谓次小生成树,顾名思义就是从生成树中取出的第二小的生成树. 我们在前面已经说过最小生成树的概念及代码实现了,所以接下来要说的次小生成树应该比较简单理解了. 求次小生成树的两种方法 1:首先求出最小生成树T,然后枚举最小生成树上的边,计算除了枚举的当前最小生成树的边以外的所有边形成的最小生成树Ti,然后求最小的Ti就是次小生成树.2:首先计算出最小生成树T,然后对最小生成树上任意不相邻

HDU1863 畅通工程---(最小生成树)

畅通工程 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 27972    Accepted Submission(s): 12279 Problem Description 省政府"畅通工程"的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可).经过调查评估,得到的统计表中列出

51Nod1601 完全图的最小生成树计数

传送门 我居然忘写题解啦!(记忆废) 不管怎么说,这题还算是一道好题啊--你觉得敦爷出的题会有水题么 -- 这题比较容易把人误导到Boruvka算法之类的东西上去(我们机房去刚D题的人一开始大多也被误导了),但仔细思考之后是可以发现问题的特殊性质的. 听说很多人是从Kruskal算法想到这道题的做法的?好吧我并不是,那我就写写我的思考过程好了-- 记得算导上有一道思考题,判断一个最小生成树算法的正确性.那个算法是这样的:把当前图的点集随意划分成两半,递归两半后选出连接两个点集的边中权值最小的一条

最小生成树求法 Prim + Kruskal

prim算法的思路 和dijkstra是一样的 每次选取一个最近的点 然后去向新的节点扩张 注意这里的扩张 不再是 以前求最短路时候的到新的节点的最短距离 而是因为要生成一棵树 所以是要连一根最短的连枝 所以关键部分修改一下 dist[u] = min(dist[u], e.cost) --->>e是连接 v 和 u的边 同样地 普同写法O(v^2) 用队列优化后O(E*logV) 1 #include <iostream> 2 #include <stdio.h> 3

UVALive-7303- Aquarium【最小生成树】【连通块】

UVALive - 7303- Aquarium 题目链接:7303 题目大意:给你一个r * c的格子,每个格子有一个 ' \ ' 或者 '/' 的墙,以及打掉墙的费用,问使得所有块联通的最小费用.(看图好理解) 题目思路:就是将他化成一个图,联通的块相当于一个点,两个点之间有一条边,边的权值为墙的费用. 转化为连通块的思路是:每个格子看成两部分,左侧和右侧.以一行来看,假设两个格子A,B.那么B格子的右侧的编号一定和A格子的左侧的编号相同.如图所示 给每个格子的左右侧标上号,然后加入边,边的

BZOJ_1016_[JSOI2008]_最小生成树计数_(dfs+乘法原理)

描述 http://www.lydsy.com/JudgeOnline/problem.php?id=1016 给出一张图,其中具有相同权值的边的数目不超过10,求最小生成树的个数. 分析 生成树的计数有一个什么什么算法... 我真的企图研究了...但是智商捉急的我实在看不懂论文... 所以最后还是写了暴力... 当然暴力也要靠正确的姿势的. 首先来看一个结论: 同一张图的所有最小生成树中,边权值相同的边的数目是一定的. 也就是说,假如某一张图的某一棵最小生成树由边权值为1,1,2,2,2,3的

poj1861 最小生成树 prim &amp; kruskal

// poj1861 最小生成树 prim & kruskal // // 一个水题,为的只是回味一下模板,日后好有个照应不是 #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <iostream> using namespace std; const int MAX_N = 1008; const int INF =