首页 > 代码库 > 九度OJ 1017 还是畅通工程
九度OJ 1017 还是畅通工程
#include <iostream>#include <string.h>#include <sstream>#include <math.h>#include <vector>#include <stack>#include <algorithm>using namespace std;struct Node{ int startPoint; int endPoint; int len; bool operator <(const Node other) const { return len<other.len?true:false; }};int findParent(int isAdded[],int point){ if(isAdded[point]==-1) return point; else return findParent(isAdded,isAdded[point]);}int main(){ int n = 0; cin>>n; while(n!=0) { Node areaPoint[5000]; int totalCost = 0; if(n==1) { cout<<totalCost<<endl; cin>>n; continue; } int isAddEd[101]; int i; for(i=0;i<101;i++) isAddEd[i] = -1; int edge = 0; for(i=0;i<n*(n-1)/2;i++) { cin>>areaPoint[i].startPoint>>areaPoint[i].endPoint>>areaPoint[i].len; } sort(areaPoint,areaPoint+n*(n-1)/2); for(i=0;i<n*(n-1)/2;i++) { int start = areaPoint[i].startPoint; int rear = areaPoint[i].endPoint; int startParent = findParent(isAddEd,start); int rearParent = findParent(isAddEd,rear); //cout<<start<<" "<<rear<<" "<<startParent<<" "<<rearParent<<endl; if(startParent == rearParent) { continue; } else { isAddEd[startParent] = rearParent; totalCost += areaPoint[i].len; edge++; if(edge==n-1) break; } } cout<<totalCost<<endl; cin>>n; } return 1;}
- 题目描述：
- 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
- 输入：
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
- 输出：
对每个测试用例，在1行里输出最小的公路总长度。
- 样例输入：
31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50
- 样例输出：
35
解题思路：
存储每一条边，以及对应的2个端点，按边的长度排序
对每一条边进行遍历，如果该边的2个端点的父节点相同，表示当前边不能加入，如果加入则会形成环，否则加入，并修改起点的父亲的父亲为终点的父亲。
每加入一条边，计数器加1，当计数器为n-1时结束循环，避免后面没必要的遍历。
九度OJ 1017 还是畅通工程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。