HDU 1232 畅通工程

HDU 1232 畅通工程
这个题目也是典型的最小生成树算法的利用,不同于其他的题目就在于其它要求的是要添加的边的最少数目,使得任意两
点都有联系,利用并查集算法 ,在题目已经给出的map基础上,统计两棵树相并的次数,即使要添加的路径的最少数目。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 int father[1001], tot;//father[i] 记录 i 的 BOSS !  
 5 //tot 统计最初至少需要添加的路径数目 ! 
 6 
 7 int find(int x)
 8 {//找 到  x 的 BOSS ! 
 9     int r = x;
10     while (r != father[r]) r = father[r];
11     return r;// 
12 }
13 
14 void join(int a, int b)
15 {//将 a 和  b 的 BOSS 统一! 
16      int fa = find(a), fb = find(b);
17      if (fa != fb)
18      {
19         father[fa] = fb;
20         tot --// 统一了一次两个阵营的  BOSS ,所以需要添加的路径的数目减一! 
21      }
22 }
23 
24 int main()
25 {
26     int n, m, x, y;
27     while (scanf("%d"&n), n)
28     {
29           scanf("%d"&m);
30           tot = n-1// 初始化 tot 等于 n 个点联通所需要的最少边的数目 ! 
31           father[n+1];
32           for (int i=1; i<=n; i++)father[i] = i;//初始化自己是自己的 BOSS ! 
33           
34           for (int i=1; i<=m; i++)
35           {
36               scanf("%d %d",&x, &y);
37               join(x, y);  
38           }
39           printf("%d\n",tot); //输出在已有基础上还需要的边的数目! 
40     }
41     return 0;
42 }
43 

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


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


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

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

资源连接

搜索

最新评论

阅读排行榜

评论排行榜