还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 70492 Accepted Submission(s): 31905
Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
当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
Huge input, scanf is recommended.
Hint
HintSource
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <algorithm> #include <iostream> #include<cstdio> #include<string> #include<cstring> #include <stdio.h> #include <queue> #include <string.h> #include <vector> #include <map> #define ME(x , y) memset(x , y , sizeof(x)) #define SF(n) scanf("%d" , &n) #define rep(i , n) for(int i = 0 ; i < n ; i ++) #define INF 0x3f3f3f3f #define mod 1024 using namespace std; typedef long long ll ; int fa[10009]; struct node{ int from , to , va ; }a[10009]; bool cmp(node a , node b) { return a.va < b.va ; } int find(int x) { return x = (fa[x] == x)? x : find(fa[x]); } void unite(int x , int y) { x = find(x) , y = find(y); if(x > y) fa[x] = y ; else fa[y] = x ; } int main() { int n ; while(~scanf("%d" , &n) && n) { int u , v , w , dis = 0 , ans = 0 ; int num = n * (n - 1) / 2; for(int i = 1 ; i <= n ; i++) fa[i] = i ; for(int i = 0 ; i < num ; i++) { scanf("%d%d%d" , &u , &v , &w); a[i].from = u , a[i].to = v , a[i].va = w ; } sort(a , a + num , cmp); for(int i = 0 ; i < num ; i++) { if(find(fa[a[i].from]) != find(fa[a[i].to])) { unite(a[i].from , a[i].to); dis += a[i].va ; ans ++ ; } if(ans == n - 1) { break ; } } printf("%d " , dis); } return 0 ; }
-
}closedge[vexCounts]
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <algorithm> #include <iostream> #include<cstdio> #include<string> #include<cstring> #include <stdio.h> #include <queue> #include <string.h> #include <vector> #include <map> #define ME(x , y) memset(x , y , sizeof(x)) #define SF(n) scanf("%d" , &n) #define rep(i , n) for(int i = 0 ; i < n ; i ++) #define INF 0x3f3f3f3f #define mod 1024 using namespace std; typedef long long ll ; int map1[109][109];//记录所有路径的距离 int dis[10009];//记录u集合到v的最小距离 int n ; int vis[10009]; int ans ; void prim() { for(int i = 1 ; i <= n ; i++) { vis[i] = 0 ; dis[i] = map1[1][i] ;//把1顶点放入u集合中，并记录该点到其他所有定点的距离 } vis[1] = 1 ;//标记1加入u集合点 for(int i = 2 ; i <= n ; i++)//要进行n-1次操作，也就是选出n-1条边 { int min = INF; int pos ; for(int j = 1 ; j <= n ; j++) { if(!vis[j] && min > dis[j])//选出u集合各点到v集合各点中最小的权值边 { min = dis[j]; pos = j ;//记录最小权值边的的点 } } vis[pos] = 1 ;//将该点放入u集合中，并标记 ans += min ;//计算最小生成树 for(int j = 1 ; j <= n ; j++)//u集合加入了新的点后，需要更新u集合各点到v集合各点的最小权值 { if(!vis[j] && map1[pos][j] < dis[j]) { dis[j] = map1[pos][j]; } } } } void init() { memset(map1 , INF , sizeof(map1)); memset(vis , 0 , sizeof(vis)); ans = 0 ; } int main() { while(~scanf("%d" , &n) && n) { init(); int num = n * (n - 1) / 2 ; int u , v , w ; for(int i = 0 ; i < num ; i++) { scanf("%d%d%d" , &u , &v , &w); if(map1[u][v] > w) map1[u][v] = map1[v][u] = w ; } prim(); printf("%d " , ans); } return 0 ; }