为什么找别人做网站,网上国网app推广经验,wordpress安装后首页字体太大,免费建网站样板手机版村村通工程#xff08;Kruskal算法#xff09;
题目描述
村村通是国家一个系统工程#xff0c;其包涵有#xff1a;公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。
村村通公路工程#xff0c;是国家为构建和谐社会#xff0c;支持新农村建设…村村通工程Kruskal算法
题目描述
村村通是国家一个系统工程其包涵有公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。
村村通公路工程是国家为构建和谐社会支持新农村建设的一项重大举措是一项民心工程。又称“五年千亿元”工程
该工程是指中国力争在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
最小生成树Kruskal算法
思路图中每个顶点各自构成一个连通分量,然后按照边的权值由小到大的顺序.依次考察边集E中的各条边。
若被考察边的两个顶点属于两个不同的连通分量则将此边加人到TE中同时把两个连通分量连接为一个连通分量;若被考察边的两个顶点属于同一个连通分量则舍去此边,以免造成回路如此下去当T中的连通分量个数为1时此连通分量便为G的一棵最小生成树。
#includebits/stdc.h
using namespace std;
struct line
{//记录边连接的两个点 且s1的下标比s2的下标小string s1,s2;//记录边的长度int path;
}lines[205];
//将边按照权值从小到大排序
bool cmp(line l1,line l2)
{return l1.pathl2.path;
}
//判断两个点是否不在同一个连通分量
bool judge(int home[],int index,mapstring,int m)
{string s1lines[index].s1;string s2lines[index].s2;int a1m[s1];int a2m[s2];if(home[a1]home[a2]) return 0;else return 1;
}
//更新home值
void changeHome(int home[],int ini,int fin,int n)
{for(int i0;in;i){if(home[i]ini) home[i]fin;}
}
int main()
{int n;cinn;//记录节点string s[205];//记录节点的下标mapstring,int m;for(int i0;in;i) {cins[i];m[s[i]]i;}int line;cinline;for(int i0;iline;i){string s1,s2;int k;cins1s2k;if(m[s1]m[s2]){lines[i].s1s1;lines[i].s2s2;}else{lines[i].s1s2;lines[i].s2s1;}lines[i].pathk;}//将边按照权值从小到大排序sort(lines,linesline,cmp);//记录所在连通分量 用该连通分量内最小的下标表示int home[205];for(int i0;in;i) home[i]i;int index0;int i;int res0;string ans;for(i0;in-1;i){//judge判断两个点是否不在同一个连通分量while(indexline!judge(home,index,m)) index;if(indexline) break;int a1m[lines[index].s1];int a2m[lines[index].s2];if(home[a1]home[a2]) swap(a1,a2);//更新home值changeHome(home,home[a2],home[a1],n);reslines[index].path;ansanslines[index].s1 lines[index].s2 to_string(lines[index].path)\n;index;}if(in-1) cout-1endl;else{coutresendl;coutans;}return 0;
}
相关文章：
