#include <stdio.h>
#include <string.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 100
#define MAX_INT 20000000
int graph[N][N];
int dist[N]; /* dist[i]表示顶点i距离已加入集合的最小距离, 如果dist[i]变为-1, 表示顶点i已加入集合 */
int n;
int prim(int u)
{
int i, p, min, total_cost, min_edge;
for (i = 0; i < n; i++) {
dist[i] = MAX_INT;
}
p = u; /* p为选种加入集合的点,初始时为u */
total_cost = 0;
for (;;) {
min = MAX_INT;
min_edge = -1;
debug("顶点%d加入集合\n", p);
dist[p] = -1;
/* 把顶点p加入集合后, 遍历所有未加入集合的顶点, 更新它们的距离, 同时找出距离最小的顶点 */
for (i = 0; i < n; i++) {
if (dist[i] >= 0) { /* 顶点i未加入集合 */
if (graph[p][i] > 0 && graph[p][i] < dist[i]) {
dist[i] = graph[p][i];
debug("更新顶点%d的距离为%d\n", i, dist[i]);
}
if (dist[i] < min) {
min = dist[i];
min_edge = i;
}
}
}
if (min_edge == -1) break;
debug("距离最小的顶点为%d, 长度为%d\n", min_edge, min);
p = min_edge;
total_cost += min;
}
return total_cost;
}
int main()
{
int i, j;
while (scanf("%d", &n) != EOF) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("%d\n", prim(0));
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1705139
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1704752
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
北大POJ2485-Highways【Prim】 解题报告+AC代码
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
NULL 博文链接:https://200830740306.iteye.com/blog/603493
poj1087贪心算法实验报告 poj1087贪心算法实验报告
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) .....
POJ各题算法分类和题目推荐.pdf
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
供初学编程基本算法的人练习使用,在poj.grids.cn上
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
北大POJ1789-Truck History【Prim】 解题报告+AC代码