HDU1233还是畅通工程

xiaoxiao2021-02-28  77

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 55392    Accepted Submission(s): 25158 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.   //最小生成树利用并查集 /* 并查集,Kruskal算法,最小生成树 */ #include<iostream> #include<cstring> #include<vector> #include<algorithm> #include <stdio.h> using namespace std; struct edge { int u, v; int cost; }; bool cmp(edge a, edge b) { return a.cost < b.cost; } int findFather(vector<int> father, int x) { int a = x; while(x != father[x]) x = father[x]; while(a != father[a]) { int z = a; a = father[a]; father[z] = x; } return x; } /*Kruskal算法求无向图的最小生成树*/ int Kruskal(int n, int m, vector<edge> &E) { /* param n: 图的顶点个数 m: 图中边的个数 E: 边的集合 */ vector<int> father(n); int ans = 0; int NumEdge = 0; for(int i = 0; i < n; i++) { father[i] = i; } sort(E.begin(), E.end(), cmp); for(int i = 0; i < m; i++) { int faU = findFather(father, E[i].u); int faV = findFather(father, E[i].v); if(faU != faV) { father[faU] = faV; ans += E[i].cost; NumEdge++; if(NumEdge == n-1) break; } } if(NumEdge != n-1) return -1; else return ans; } int main() { vector<edge> E; int n, m; int xx, yy, zz; while(scanf("%d", &n)!=EOF && n) { m = n*(n-1)/2; edge EE; for(int i = 0; i < m; i++) { cin>>xx>>yy>>zz; EE.u=xx - 1; EE.v=yy - 1; EE.cost=zz; E.push_back(EE); } int res = Kruskal(n, m, E); cout << res << endl; E.clear(); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-1949984.html

最新回复(0)