首页 > 代码库 > 数据结构与算法问题 sdut oj 2144 最小生成树
数据结构与算法问题 sdut oj 2144 最小生成树
题目描述
有n个城市,其中有些城市之间可以修建公路,修建不同的公路费用是不同的。现在我们想知道,最少花多少钱修公路可以将所有的城市连在一起,使在任意一城市出发,可以到达其他任意的城市。
输入
输入包含多组数据,格式如下。
第一行包括两个整数n m,代表城市个数和可以修建的公路个数。(n<=100)
剩下m行每行3个正整数a b c,代表城市a 和城市b之间可以修建一条公路,代价为c。
输出
每组输出占一行,仅输出最小花费。
示例输入
3 2 1 2 1 1 3 1
示例输出
2
#include <iostream> using namespace std; const int INTIFIY = 65535; typedef struct graph { int vex[200]; int adj[200][200]; int numvex, numedge; }graph; void create(graph * g) { int w, j, i,k; cin >> g->numvex >> g->numedge; for ( i = 1; i<g->numedge; i++) for (j = 1; j<g->numedge; j++) g->adj[i][j] = INTIFIY; for (i = 1; i <= g->numvex; i++) g->vex[i] = i; for ( k = 0; k<g->numedge; k++) { cin >> i >> j >> w; g->adj[i][j] = w; g->adj[j][i] = g->adj[i][j]; } } void prim(graph * g) { int min, i, k, j, num = 0; int lowcost[200]; int adj[200]; lowcost[1] = 0; //存放权值 adj[1] = 1; //每个结点的前驱 for (i = 2; i<=g->numvex; i++) { lowcost[i] = g->adj[1][i]; adj[i] = 0; } for (i = 2; i<=g->numvex; i++) { min = INTIFIY; j = 2; while (j<=g->numvex) { if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; } j++; num += min; } lowcost[k] = 0; for (i = 2; i<=g->numvex; i++) { if (lowcost[i] != 0 && lowcost[i]>g->adj[k][i]) { lowcost[i] = g->adj[k][i]; adj[i] = k; } } } cout << num << endl; } int main() { graph *g = new graph; create(g); prim(g); system("pause"); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。