题目描述

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

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

该工程是指中国力争在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

NOTICE：

普利姆算法（Prim）主要有以下几点需要注意：（1）所需的变量有visited数组，记录顶点是否加入到U集合中；dis数组，表示从U到V-U中各顶点的最小权值；adj数组，使dis取最小的U中邻接点；mindis，dis中的最小值；minindex，dis中的最小值的下标，weightsum，最小生成树的权值；（2）初始化时将所有的visited初始化为0，所有的dis初始化为MAX，minindex初始化为起点；（3）循环n-1次，每次更新两个任务，更新dis、adj数组和找到新的最小的dis。

#include <iostream>
using namespace std;
#define MAX 66535struct edge//方便输出而定义的类
{string start, end;int weight;
};
class Graph
{
private:string* data;int** Matrix;int vertexnum;int edgenum;string v;//普里姆算法的起点int find(string s)//根据顶点信息，返回顶点下标{for (int i = 0; i < vertexnum; i++)if (s == data[i])return i;}
public:Graph(){cin >> vertexnum;data = new string[vertexnum];for (int i = 0; i < vertexnum; i++)cin >> data[i];Matrix = new int* [vertexnum];for (int i = 0; i < vertexnum; i++)Matrix[i] = new int[vertexnum];for (int i = 0; i < vertexnum; i++)for (int j = 0; j < vertexnum; j++)Matrix[i][j] = MAX;cin >> edgenum;string s1, s2;int w;for (int i = 0; i < edgenum; i++){cin >> s1 >> s2 >> w;Matrix[find(s1)][find(s2)] = w;Matrix[find(s2)][find(s1)] = w;}cin >> v;}~Graph(){delete[]data;for (int i = 0; i < vertexnum; i++)delete[]Matrix[i];delete[]Matrix;}void MinTree_Prim(){int* visited = new int[vertexnum];int* dis = new int[vertexnum];int* adj = new int[vertexnum];int mindis;int min_index;int weight_sum = 0;edge* result = new edge[vertexnum - 1];//根据输出要求，定义一个数组方便输出，元素个数是n-1个（最小生成树）int edge_index = 0;//初始化for (int i = 0; i < vertexnum; i++){visited[i] = 0;dis[i] = MAX;}min_index = find(v);//循环n-1次for (int t = 0; t < vertexnum-1; t++){visited[min_index] = 1;//更新for (int i = 0; i < vertexnum; i++){if (!visited[i] && Matrix[min_index][i] < dis[i]){dis[i] = Matrix[min_index][i];adj[i] = min_index;}}//找到最小的dismindis = MAX;for (int i = 0; i < vertexnum; i++)if (!visited[i] && dis[i] < mindis){mindis = dis[i];min_index = i;}weight_sum += dis[min_index];result[edge_index].start = data[adj[min_index]];result[edge_index].end = data[min_index];result[edge_index].weight = dis[min_index];edge_index++;}//输出cout << weight_sum << endl;for (int i = 0; i < vertexnum - 1; i++){cout << result[i].start << " ";cout << result[i].end << " ";cout << result[i].weight << endl;}}
};int main()
{Graph g;g.MinTree_Prim();return 0;
}