题目描述
"村村通"是国家一个系统工程，其包涵有：公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。
村村通公路工程，是国家为构建和谐社会，支持新农村建设的一项重大举措，是一项民心工程。又称“五年千亿元”工程
该工程是指中国力争在5年时间实现所有村庄通沥青路或水泥路，以打破农村经济发展的交通瓶颈，解决9亿农民的出行难题。
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
要求用Kruskal算法求解
输入
第1行：顶点数n
第2行：n个顶点编号
第3行：边数m
接着m行：m条边信息，格式为：顶点1 顶点2 权值
输出
第1行：输出最小生成树的权值之和
接着n-1行对应n-1条边信息
如果能找到最小生成树，按树的生长顺序输出, 边顶点按数组序号升序输出
如果输入数据不足以保证畅通，则直接输出−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
输出样例1
15 v1 v3 1 v4 v6 2 v2 v5 3 v3 v6 4 v2 v3 5
思路分析
克鲁斯卡尔算法的思想是逐步选择边来构建最小生成树。具体步骤如下：
- 将图中的所有边按照权值从小到大进行排序。
- 从权值最小的边开始，依次考虑每条边：
- 如果该边的两个顶点不在同一个连通分量中，则选择该边加入最小生成树，并合并这两个顶点所在的连通分量。
- 如果该边的两个顶点已经在同一个连通分量中，则舍弃该边，以避免形成环路。
- 重复步骤2，直到最小生成树中包含图中的所有顶点为止。
通过这种方式，克鲁斯卡尔算法能够找到一个连通图的最小生成树，并且保证总权值最小。算法的关键在于选择边的过程中保证不会形成环路，以确保最终生成的树是连通的。
AC代码
代码语言：javascript复制#include<iostream>
#include<vector>
using namespace std;
const int MaxLength = 100;
struct Vertex {
int index;
string data;
} vertex[MaxLength];
struct Path {
int head;
int tail;
};
class Map {
int matrix[MaxLength][MaxLength] = {0};
int vertexNumber;
int sumCost = 0;
vector<Path> path;
int close[MaxLength];
int count=0;
public:
Map() {
cin >> vertexNumber;
for(int i=0;i<vertexNumber;i )
close[i]=i;
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;
}
Kruskal();
}
int GetIndex(string &data) {
for (int i = 0; i < vertexNumber; i )
if (vertex[i].data == data)
return i;
}
void Merge(int&x,int&y){
close[GetRoot(y)]= GetRoot(x);
}
int GetRoot(int&x){
if(close[x]==x)
return x;
return GetRoot(close[x]);
}
void Kruskal() {
for(int k=0;k<vertexNumber-1;k ){
int minCost=0x3f3f3f3f,tail=0,head=0;
for(int i=0;i<vertexNumber;i )
for(int j=i 1;j<vertexNumber;j )
if(matrix[i][j]&&minCost>matrix[i][j]&& GetRoot(i)!= GetRoot(j)){
head=i;
tail=j;
minCost=matrix[i][j];
}
Merge(head,tail);
Path pass = {head, tail};
path.push_back(pass);
sumCost = minCost;
if(tail||head)
count ;
}
if(count==vertexNumber-1){
cout << sumCost << endl;
for (auto &it: path)
cout << vertex[it.head].data << ' ' << vertex[it.tail].data << ' ' << matrix[it.head][it.tail] << endl;
}
else cout<<"-1"<<endl;
}
};
int main() {
Map test;
}
