HDU 1233 还是畅通工程

HDU 1233 还是畅通工程
题目意思就是给你一个有n个点的图,给出n *(n-1)/ 2 条边的信息,包括边的端点和边的长度,要求
在满足所有点在同一个连通分支上的前提下,选择最短的道路来修建。典型的最小生成树算法,同样,问题
规模不大,直接矩阵就可以胜任。
 1 #include<stdlib.h>
 2 #include<stdio.h>
 3 #include<string.h> 
 4 
 5 const int MAX = 100000000;
 6 int map[101][101], MIN, sum;
 7 // map[i][j] 记录从点 i 到点 j 的距离 ! 
 8 
 9 int main()
10 {
11     int n, x, y, m, v[101], flag, dis;
12     while (scanf("%d"&n), n)
13     {
14           map[n][n];
15           memset(map, 0sizeof(map));//数组清零 
16           m = (n*(n-1))/2;
17           for (int i=0; i<m; i++)
18           { //输入并处理边的信息 
19               scanf("%d %d %d"&x, &y, &dis);
20              map[x-1][y-1= map[y-1][x-1= dis;
21           }
22           for (int i=0; i<n; i++)map[i][i] = MAX;
23           //建图完成 !
24           v[n];
25           memset(v, 0sizeof(v));
26           v[0= 1;
27           sum = 0
28           for (int i=1; i<n; i++)
29           {//prim 算法求最小生成树 
30               MIN = 10000000
31               for (int j=0; j<n; j++)
32               {
33                   if (!v[j] && map[0][j] < MIN)
34                   {
35                      MIN = map[0][j];
36                      flag = j;
37                   }
38               }
39               sum += MIN; 
40               v[flag] = 1;
41               for (int j=0; j<n; j++)
42               {
43                   if (!v[j] && map[0][j] > map[flag][j])
44                   {
45                      map[0][j] = map[flag][j];
46                   }
47               }
48           }
49           printf("%d\n",sum);
50     }
51     return 0;
52 }
53 


posted on 2011-07-18 09:20 AK 阅读(2353) 评论(0)  编辑 收藏 引用 所属分类: 最小生成树和并查集


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

资源连接

搜索

最新评论

阅读排行榜

评论排行榜