第一次 Prim 思想初步实践版
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1233
Name : 1233 还是畅通工程
Date : Sunday, February 5, 2012
Time Stage : one hour
Result:
5316885 2012-02-05 11:43:47 Accepted 1233
203MS 212K 1639 B
C++ pyy
5316784 2012-02-05 11:19:20 Wrong Answer 1233
93MS 212K 1655 B
C++ pyy
Test Data :
Review :
这个程序的耗时比较大,因为是我根据 Prim 算法的思想自己写的代码,最原始,也是最慢的。
它每次都要遍历两个集合中的每个元素,并且外面还有一个大循环,总共便是接近O(n^3)的耗时。
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (103)
#define MAXE (MAXN*MAXN)
#define DEBUG /##/
int n, m ;
int used[MAXN], q[MAXN] ;
int map[MAXN][MAXN] ;
int Prim ()
{
int i, j, sum, MinPath, iMinPath, nCnt ;
MEM(used, 0) ;
used[1] = true ;
nCnt = 0 ;
sum = 0 ;
q[nCnt++] = 1 ;
while (nCnt < n)
{
int end = nCnt ;
MinPath = INF ; // 一开始这个放到第一个for里面去了,结果WA
// 遍历集合,找出到剩余各点的最短路径
for (j = 0 ; j < end ; ++j)
{
int t = q[j] ;
for (i = 1 ; i <= n ; ++i)
{
if (!used[i] && map[t][i] < MinPath)
{
MinPath = map[t][i] ;
iMinPath = i ;
}
}
}
if (INF > MinPath) // 一开始这个放到第一个for里面去了,结果WA
{
used[iMinPath] = true ;
q[nCnt++] = iMinPath ;
sum += MinPath ;
}
}
return sum ;
}
int main ()
{
int i ;
int x, y, c ;
while (scanf ("%d", &n), n)
{
MEM(map, INF) ;
m = n*(n-1)/2 ;
for (i = 1 ; i <= m ; ++i)
{
scanf ("%d%d%d", &x, &y, &c) ;
map[x][y] = map[y][x] = min(c, map[x][y]) ;
}
printf ("%d\n", Prim ()) ;
}
return 0 ;
}
第一次 Prim 参考解题报告版
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1233
Name : 1233 还是畅通工程
Date : Sunday, February 5, 2012
Time Stage : one hour
Result:
5316958 2012-02-05 12:02:07 Accepted 1233
93MS 212K 1757 B
C++ pyy
Test Data :
Review :
此程序的思想是,先建立一个数组保存从 集合1 到 集合2 的最短距离。
一开始,集合1的点是 1,集合2的点是除1以外的点。然后一次 for 循环保存从
点1 到其他各点的距离。……详情见注释
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (103)
#define MAXE (MAXN*MAXN)
#define DEBUG /##/
int n, m ;
int used[MAXN], q[MAXN], dist[MAXN] ;
int map[MAXN][MAXN] ;
int Prim ()
{
int i, j, sum, MinPath, iMinPath ;
MEM(used, 0) ;
sum = 0 ;
// 保存 1 点到其他点的距离
for (i = 1 ; i <= n ; ++i)
dist[i] = map[1][i] ;
used[1] = true ; // 标记此点已经在集合1中
for (j = 1 ; j <= n - 1 ; ++j)
{
// 求出集合1 到其他各点的距离的最小值
MinPath = INF ;
for (i = 1 ; i <= n ; ++i)
{
if (!used[i] && dist[i] < MinPath)
{
MinPath = dist[i] ;
iMinPath = i ;
}
}
// 标记此点已经加入到集合1中
used[iMinPath] = true ;
sum += dist[iMinPath] ;
// 加入 iMinPath 点后,更新集合到其他点的距离
for (i = 1 ; i <= n ; ++i)
{
if (!used[i] && dist[i] > map[iMinPath][i])
dist[i] = map[iMinPath][i] ;
}
}
return sum ;
}
int main ()
{
int i ;
int x, y, c ;
while (scanf ("%d", &n), n)
{
MEM(map, INF) ;
m = n*(n-1)/2 ;
for (i = 1 ; i <= m ; ++i)
{
scanf ("%d%d%d", &x, &y, &c) ;
map[x][y] = map[y][x] = min(c, map[x][y]) ;
}
printf ("%d\n", Prim ()) ;
}
return 0 ;
}
分享到:
相关推荐
代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小...
最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++
使用Prim算法编写的最小生成树(C语言),为更好地学习数据结构
Prim最小生成树Prim最小生成树Prim最小生成树
最小生成树prim最小生成树prim最小生成树prim最小生成树prim
最小生成树之prim
实现构造最小生成树的Prim算法
问题描述:给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。基本要求:1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义...
prim算法 Kruskal算法分别实现最小生成树
利用c++编程实现,最小生成树的Prim算法,
最小生成树的Prim算法 /2,Prim算法的描述:// 假如N=(V,{E})是连通网,TE是N上最小生成树中边得集合。算法从U={u0}(u0是V中的元素),TE={}开始,重复执行下述操作:// 在所有u属于U,v属于V-U的边(u,v)属于E...
普里姆算法通过寻找无向图中权值最小的边,并且将其组合成最小生成树,也就是图的相对最短路径,同时将最小生成树以点集的形式输出,便于观察
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
基于MATLAB的最小生成树Prim算法 源代码程序.rar
第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小...
最小生成树的经典算法。我在代码中加入了文字解释。并以算法导论第二版书中例子为例,得到了相同结果。代码很完整,也有结果显示环节。
最小生成树的prim算法
最小生成树,Prim算法的使用(邻接矩阵实现)
最小生成树(Prim,Kruskal)C++代码实现 (可运行,含测试用例,有输出,注释详细) 对于一个带权连通图,生成树不同,树中各边上权值总和也不同,权值总和最小的生成树则称为图的最小生成树。
基于matlab的最小生成树的prim算法,有详细的解释,可直接运行