【id:746】【20分】C. 村村通工程（Prim算法）

大家好，欢迎来到IT知识分享网。

题目描述

“村村通”是国家一个系统工程，其包涵有：公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。

村村通公路工程，是国家为构建和谐社会，支持新农村建设的一项重大举措，是一项民心工程。又称“五年千亿元”工程

该工程是指中国力争在5年时间实现所有村庄通沥青路或水泥路，以打破农村经济发展的交通瓶颈，解决9亿农民的出行难题。

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

要求用Prim算法求解

输入

第1行：顶点数n

第2行：n个顶点编号

第3行：边数m

接着m行：m条边信息，格式为：顶点1 顶点2 权值

最后一行：Prim算法的起点v

输出

第1行：输出最小生成树的权值之和

接着n-1行对应n-1条边信息

按树的生长顺序输出

输入输出样例

输入样例1 <-复制 6 v1 v2 v3 v4 v5 v6 10 v1 v2 6 v1 v3 1 v1 v4 5 v2 v3 5 v2 v5 3 v3 v4 5 v3 v5 6 v3 v6 4 v4 v6 2 v5 v6 6 v1 输出样例1 15 v1 v3 1 v3 v6 4 v6 v4 2 v3 v2 5 v2 v5 3

AC代码

#include<iostream> #include<algorithm> using namespace std; string dian[20]; int n, m; int juzhen[20][20]; struct bian { string a, b; int w; }; bian jieguo[20]; int k = 0; int weight = 0; int xun(string a) { for (int i = 0; i < n; i++) if (a == dian[i]) return i; } void show() { int i, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) { cout << juzhen[i][j] << " "; if (j == n - 1) cout << endl; } cout << endl; } void prim(string a) { int flag = 1; int aa = xun(a); for (int i = 0; i < n; i++) //起始顶点的那一列不要忘了清除 juzhen[i][aa] = 0; int shu = 0; while (flag) { shu++; juzhen[aa][n] = 1; int i, j; int min = 100; int nextj; for (i = 0; i < n; i++) { if (juzhen[i][n] == 1) { for (j = 0; j < n; j++) if (juzhen[i][j] < min && juzhen[i][j] != 0) { min = juzhen[i][j]; aa = i; nextj = j; } } } jieguo[k].a = dian[aa]; jieguo[k].b = dian[nextj]; jieguo[k].w = juzhen[aa][nextj]; weight += jieguo[k].w; k++; for (i = 0; i < n; i++) juzhen[i][nextj] = 0; //show(); flag = -1; for (i = 0; i < n; i++) if (juzhen[i][n] == 0) flag++; aa = nextj; } } int main() { int i, j; cin >> n; for (i = 0; i < n; i++) cin >> dian[i]; for (i = 0; i < n; i++) for (j = 0; j <=n; j++) juzhen[i][j] = 0; cin >> m; string a, b; for (i = 0; i < m; i++) { cin >> a >> b; int aa = xun(a), bb = xun(b); cin >> juzhen[aa][bb]; juzhen[bb][aa] = juzhen[aa][bb]; } //show(); cin >> a; prim(a); cout << weight << endl; for (i = 0; i < k; i++) cout << jieguo[i].a << " " << jieguo[i].b << " " << jieguo[i].w << endl; }

（by 归忆）