首页 > 代码库 > 还是畅通工程[HDU1233]
还是畅通工程[HDU1233]
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 41897 Accepted Submission(s): 19126
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.
#include <stdio.h>#include <algorithm>#include <math.h>#include <string.h>using namespace std;class Union_Find_Set {#define MAX_UNION_FIND_SET_SIZE 105public: int setSize; int father[MAX_UNION_FIND_SET_SIZE]; Union_Find_Set() { setSize = 0; } Union_Find_Set(int x) { setSize = x; clear(x); } void clear(int x) { for (int i = 0; i < x; i++) { father[i] = i; } } int getFather(int x) { if (x != father[x]) { father[x] = getFather(father[x]); } return father[x]; } bool merge(int a, int b) { a = getFather(a); b = getFather(b); if (a != b) { father[a] = b; return true; } else { return false; } } int countRoot() { int ret = 0; for (int i = 0; i < setSize; i++) { if (father[i] = i) { ret++; } } return ret; }};class Kruskal {#define Kruskal_MAXN 100#define Kruskal_MAXM 10005public: Union_Find_Set ufs; int x[Kruskal_MAXM], y[Kruskal_MAXM], w[Kruskal_MAXM], N, M; Kruskal() { N = 0; M = 0; } void clear() { N = 0; M = 0; } void addEdge(int a, int b, int c) { x[M] = a; y[M] = b; w[M] = c; M++; x[M] = b; y[M] = a; w[M] = c; M++; } void sort(int l, int r) { int i = l, j = r, m = w[(l + r) >> 1], t; do { while (w[i] < m) { i++; } while (m < w[j]) { j--; } if (i <= j) { t = x[i]; x[i] = x[j]; x[j] = t; t = y[i]; y[i] = y[j]; y[j] = t; t = w[i]; w[i] = w[j]; w[j] = t; i++; j--; } } while (i <= j); if (l < j) { sort(l, j); } if (i < r) { sort(i, r); } } int MST() { sort(0, M - 1); ufs.clear(N + 1); int cnt = 0, ret = 0; for (int i = 0; i < M; i++) { if (cnt == N - 1) { return ret; } if (ufs.getFather(x[i]) != ufs.getFather(y[i])) { ufs.merge(x[i], y[i]); ret += w[i]; cnt++; } } if (cnt == N - 1) { return ret; } else { return -1; } }};Kruskal Kr;int main() { int n; while (scanf("%d", &n) != EOF) { if (n == 0) { break; } Kr.clear(); Kr.N=n; for (int i = 1; i < n; i++) for (int j = i + 1; j <= n; j++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); Kr.addEdge(a, b, c); } printf("%d\n", Kr.MST()); } return 0;}
还是畅通工程[HDU1233]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。