村村通工程（Prim算法）
“村村通“是国家一个系统工程，其包涵有：公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。
村村通公路工程，是国家为构建和谐社会，支持新农村建设的一项重大举措，是一项民心工程。又称“五年千亿元”工程
该工程是指中国力争在5年时间实现所有村庄通沥青路或水泥路，以打破农村经济发展的交通瓶颈，解决9亿农民的出行难题。
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
第3行：边数m
输入样例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算法
最小生成树：在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此的边权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。最小生成树其实是最小权重生成树的简称。（简而言之就是把一个图变成一棵树，并且树中的边权和最小，还能连接所有顶点）
Prim算法：其基本思想是对图G(V,E)设置集合S，存放已被访问的顶点，然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点（记为u），访问并加入集合S。之后，令顶点u为中介点，优化所有从u能到达的顶点v与集合S之间的最短距离。这样的操作执行n次（n为顶点个数），直到集合S已包含所有顶点。
可以发现，prim算法的思想与最短路径中Dijkstra算法的思想几乎完全相同，只是在涉及最短距离时使用了集合S代替 Dijkstra算法中的起点s。
#include<bits/stdc++.h>
#define INF 99999999;
using namespace std;
struct array
{
//记录到达的最短距离是到集合中哪个点
string connection;
//记录到达集合S中的点的最短距离
int r=INF;
}arr[205];
//对V-S集合更新
//index即新加的点的下标 now是新加的点
void change(int a[][205],string now,int index,int n)
{
arr[index].r=0;
for(int i=0;i<n;i++)
{
if(!arr[i].r||!a[index][i]) continue;
if(a[index][i]<arr[i].r)
{
arr[i].r=a[index][i];
arr[i].connection=now;
}
}
}
int ans=0;
string res="";
//找到最短的一条路径返回其点
string cmp(int a[][205],int n,string s[])
{
int small=INF-1;
string name;
string first;
for(int i=0;i<n;i++)
{
if(arr[i].r!=0&&arr[i].r<small)
{
small=arr[i].r;
name=s[i];
first=arr[i].connection;
}
}
ans+=small;
res=res+first+" "+name+" "+to_string(small)+"n";
return name;
}
int main()
{
int n;
cin>>n;
//记录顶点
string s[205];
//记录顶点的下标
map<string,int> m;
for(int i=0;i<n;i++)
{
cin>>s[i];
m[s[i]]=i;
}
int line;
cin>>line;
//邻接矩阵
int a[205][205]={0};
for(int i=0;i<line;i++)
{
string s1,s2;
int k;
cin>>s1>>s2>>k;
int a1=m[s1];
int a2=m[s2];
a[a1][a2]=k;
a[a2][a1]=k;
}
string sta;
cin>>sta;
int now=m[sta];
for(int i=0;i<n-1;i++)
{
//对V-S集合更新
change(a,sta,now,n);
//找到最短的一条路径返回其点
sta=cmp(a,n,s);
now=m[sta];
}
cout<<ans<<endl;
cout<<res;
return 0;
}
原文地址:https://blog.csdn.net/m0_74053777/article/details/134654685
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_19561.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
