本文共 980 字,大约阅读时间需要 3 分钟。
还是畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 39902 Accepted Submission(s): 18125 Problem Description 某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。 Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。 当N为0时,输入结束,该用例不被处理。 Output 对每个测试用例,在1行里输出最小的公路总长度。 Sample Input 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 Sample Output 3 5 Hint Hint Huge input, scanf is recommended. Source 浙大计算机研究生复试上机考试-2006年 Recommend JGShining | We have carefully selected several similar problems for you: 1102 1875 1879 1301 1162将每两个村庄的路段的长度保存 用sort从小到大排序 并查集查看n-1条路即可 及时更换父节点 防止超时
#include#include #include #include #include using namespace std;struct ac{ int x; int y; int v;}a[5000];int pre[150];bool cmp(ac p,ac q){ return p.v
转载地址:http://txfci.baihongyu.com/