题目描述
"村村通"是国家一个系统工程，其包涵有：公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。
村村通公路工程，是国家为构建和谐社会，支持新农村建设的一项重大举措，是一项民心工程。又称“五年千亿元”工程
该工程是指中国力争在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
思路分析
Prim算法的思想如下：
- 选择一个起始顶点作为初始集合，可以是任意一个顶点。
- 将该起始顶点加入到最小生成树的顶点集合中。
- 从已加入最小生成树的顶点集合中，选择一个顶点u，将与顶点u相连且权值最小的边（u, v）加入到候选边集合。
- 从候选边集合中选择权值最小的边（u, v），将顶点v加入到最小生成树的顶点集合中，同时将边（u, v）加入到最小生成树的边集合中。
- 重复步骤3和步骤4，直到最小生成树包含图中的所有顶点为止。
通过这种方式，Prim算法逐渐扩展最小生成树的顶点集合，保证每一步都选择了与已加入顶点集合具有最小权值的边。最终得到的最小生成树是以起始顶点为根节点的一棵树，并且总权值最小。
需要注意的是，Prim算法的实现通常需要使用优先队列（最小堆）来高效地选择权值最小的边。
AC代码
代码语言：javascript复制#include<iostream>
#include<vector>
using namespace std;
const int MaxLength = 100;
struct Vertex {
int index;
string data;
} vertex[MaxLength];
struct Close {
int adjacent;
int cost = 0x3f3f3f3f;
} close[MaxLength];
struct Path {
int head;
int tail;
};
class Map {
int matrix[MaxLength][MaxLength] = {0};
int vertexNumber;
int sumCost = 0;
vector<Path> path;
public:
Map() {
cin >> vertexNumber;
for (int i = 0; i < vertexNumber; i ) {
cin >> vertex[i].data;
vertex[i].index = i;
}
int edgeNumber;
cin >> edgeNumber;
for (int i = 0; i < edgeNumber; i ) {
string tail, head;
int cost;
cin >> tail >> head >> cost;
matrix[GetIndex(tail)][GetIndex(head)] = matrix[GetIndex(head)][GetIndex(tail)] = cost;
}
string start;
cin >> start;
Prim(GetIndex(start));
}
int GetIndex(string &data) {
for (int i = 0; i < vertexNumber; i )
if (vertex[i].data == data)
return i;
}
void Prim(int start) {
for (int i = 0; i < vertexNumber; i )
if (matrix[start][i])
close[i] = {start, matrix[start][i]};
else close[i].adjacent = start;
close[start].cost = 0;
for (int i = 1; i < vertexNumber; i ) {
int minCost = 0x3f3f3f3f, next;
for (int j = 0; j < vertexNumber; j )
if (minCost > close[j].cost && close[j].cost) {
minCost = close[j].cost;
next = j;
}
close[next].cost = 0;
Path pass = {close[next].adjacent, next};
path.push_back(pass);
sumCost = minCost;
for (int j = 0; j < vertexNumber; j )
if (close[j].cost > matrix[next][j] && matrix[next][j])
close[j] = {next, matrix[next][j]};
}
cout << sumCost << endl;
for (auto &it: path)
cout << vertex[it.head].data << ' ' << vertex[it.tail].data << ' ' << matrix[it.head][it.tail] << endl;
}
};
int main() {
Map test;
}
