devbox
码创造者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

(树的专题整理)_hdu树专题

作者：码创造者 | 2024-07-05 01:48:13

赞

踩

hdu树专题


           这一篇博客继续以一些OJ上的题目为载体，对树专题进行整理整理一下。会陆续的更新。。。


一、树的遍历

树的定义：连通的无回路的无向图。


例题

1、POJ 2255 Tree Recovery 树的恢复

题目分析：

        这道题抽象一下就是：“由树的前序遍历和中序遍历顺序确定输的后序遍历顺序”。其实我们很早之前就在各种资料上看到过以下这句话，“由输的前序遍历(或后序遍历)和中序遍历序列，我们就能唯一确定一个二叉树”。。但是算法思想到底是怎么样的，实现又怎么实现，我想很多人也就不怎么去探究了，也就是仅仅的记住这句话，当做是定理一样的记住。。。

      以下给出由前序遍历序列和中序遍历序列得到后序遍历序列的算法。

       描述如下：首先由前序遍历序列的第一个节点确定根节点。然后到中序遍历序列中找到该节点。然后输出该节点前面的元素的个数，接着到前序遍历序列中数同样个数的元素(除开第一个根节点)。。。这时候就得到了根节点、左子树的前序遍历序列和中序遍历虚列、右子树的前序遍历序列和中序遍历序列。   。。接下来干的活就是不断的递归。。。。。

      实现如下：

  1. /**
  2.  * 由前序序列和中序序列得到后序序列
  3.  */
  4. string solve(string pre,string in){
  5. 	if(in.length() == 1){//递归的结束条件
  6. 		return in;
  7. 	}else if(in.length() == 0){
  8. 		return "";
  9. 	}
  10.  
  11. 	int m = in.find(pre[0]);//在中序序列中找到根节点的位置
  12. 	//后序遍历的遍历次序是: 后序遍历左子树、后序遍历右子树、输出根节点的信息
  13. 	return solve(pre.substr(1,m),in.substr(0,m)) + solve(pre.substr(m+1),in.substr(m+1)) + pre[0];
  14. }


这道题的解法如下：

  1. /*
  2.  * POJ_2255_1.cpp
  3.  *
  4.  *  Created on: 2014年6月8日
  5.  *      Author: Administrator
  6.  */
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <string>
  10.  
  11. using namespace std;
  12.  
  13. /**
  14.  * 由前序序列和中序序列得到后序序列
  15.  */
  16. string solve(string pre,string in){
  17. 	if(in.length() == 1){//递归的结束条件
  18. 		return in;
  19. 	}else if(in.length() == 0){
  20. 		return "";
  21. 	}
  22.  
  23. 	int m = in.find(pre[0]);//在中序序列中找到根节点的位置
  24. 	//后序遍历的遍历次序是: 后序遍历左子树、后序遍历右子树、输出根节点的信息
  25. 	return solve(pre.substr(1,m),in.substr(0,m)) + solve(pre.substr(m+1),in.substr(m+1)) + pre[0];
  26. }
  27.  
  28. int main(){
  29. 	string back;
  30. 	string pre;
  31. 	string in;
  32. 	while(cin >> pre >> in){
  33. 		back = solve(pre,in);
  34. 		cout << back <<endl;
  35. 	}
  36.  
  37.  
  38. 	return 0;
  39. }
  40.  
  41.


   

二、图的最小生成树

     求无向图的最小生成树主要有两种算法：Prim算法和kruscal算法。以下分别介绍着两种算法。

     无向图的最下生成树问题通俗点讲就是：“求n个点连通的最小费用”


     1、Prim算法

      描述：

      1）从图中选一个点当做起始点(一般选“1”这个点)。加入到最小生成树中

      2）寻找与该点相连的边中权值最小的那条边，并将该边的另外一个点加入到最小生成树中。

      3）不断的重复步骤2）直到所有的点都在最小生成树中。


有人会说，Prim算法和dijkstra算法特别的像。除了最后那一部分基本事实一模一样的

prim写法：

  1. for(j = 1 ; j <= n ; ++j){
  2. 			if(!s[j] && dis[j] > map[pos][j]){
  3. 				dis[j] = map[pos][j];
  4. 			}
  5. 		}


dijkstra的写法：

  1. for (j = 1; j < maxn; ++j) {
  2. 			if (!s[j] && dis[j] > dis[pos] + map[pos][j]) {
  3. 				dis[j] = dis[pos] + map[pos][j];
  4. 			}
  5. 		}

其实他们的差异主要是在松弛的部分。prim的是 

  1. if(!s[j] && dis[j] > map[pos][j]){
  2. 				dis[j] = map[pos][j];
  3. 			}

因为这是求的是最小生树到未在最小生成树中的点的距离(不太准确地讲就是求一棵树都某一个点的距离，而不是dijkstra中的某一个点到未在集合中的另一个点的距离)。



      算法实现：

      

  1. int n, m;
  2.  
  3. /**
  4.  * 使用prim算法生成无向图的最小生成树
  5.  */
  6. int prim() {
  7. 	int sum = 0;
  8.  
  9. 	int i;
  10. 	for (i = 2; i <= n; ++i) {//初始化
  11. 		p[i] = false;//所有的点(除1外,默认使用1作为起始点)都不在Va集合中
  12. 		dis[i] = map[1][i];
  13. 		pre[i] = 1;
  14. 	}
  15.  
  16. 	dis[1] = 0;
  17. 	p[1] = true;
  18.  
  19. 	for (i = 1; i <= n - 1; ++i) {//循环n-1次，每次加入一个点
  20. 		int min = inf;
  21. 		int k = 0;
  22.  
  23. 		int j;
  24. 		for (j = 1; j <= n; ++j) {//求出边权值最小的那个点
  25. 			if (!p[j] && dis[j] < min) {
  26. 				min = dis[j];
  27. 				k = j;
  28. 			}
  29. 		}
  30.  
  31. 		if(k == 0){//没有电可以拓展,图G不连通
  32. 			return -10;
  33. 		}
  34.  
  35. 		sum += dis[k];
  36.  
  37. 		p[k] = true;//将点k加入到最小生成树中
  38.  
  39. 		for (j = 1; j <= n; ++j) {
  40. 			if (!p[j] && dis[j] > map[k][j]) {
  41. 				dis[j] = map[k][j];
  42. 				pre[j] = k;
  43. 			}
  44. 		}
  45. 	}
  46.  
  47. 	return sum;
  48. }

      时间复杂度：O(n^2)

      空间复杂度：O(n^2)

      基本结构：

  1. /**
  2.  * prim算法的基本结构
  3.  */
  4. int map[maxn][maxn];//map[i][j]: 表示i到j这条边的距离
  5. int p[maxn];//p[i]: 表示idian是否在Va集合(最小生成树的集合)中
  6. int dis[maxn];//最小生成树中包含节点i最短边的权值
  7. int pre[maxn];//最小生成树中包含节点i的最短边
  8.  
  9. int n, m;

      基本条件： 点数、 边数、 以及各边的权值


  注意：prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。

Ex:

看了上面一大段文字是不是感觉有点晕啊，为了更好理解我在这里举一个例子，示例如下：

 

（1）图中有6个顶点v1-v6，每条边的边权值都在图上；在进行prim算法时，我先随意选择一个顶点作为起始点，当然我们一般选择v1作为起始点，好，现在我们设U集合为当前所找到最小生成树里面的顶点，TE集合为所找到的边，现在状态如下：

U={v1}； TE={}；

（2）现在查找一个顶点在U集合中，另一个顶点在V-U集合中的最小权值，如下图，在红线相交的线上找最小值。

通过图中我们可以看到边v1-v3的权值最小为1，那么将v3加入到U集合，（v1，v3）加入到TE，状态如下：

U={v1，v3}； TE={（v1，v3）}；

（3）继续寻找，现在状态为U={v1，v3}； TE={（v1，v3）}；在与红线相交的边上查找最小值。

我们可以找到最小的权值为（v3，v6）=4，那么我们将v6加入到U集合，并将最小边加入到TE集合，那么加入后状态如下：

U={v1，v3，v6}； TE={（v1，v3），（v3，v6）}； 如此循环一下直到找到所有顶点为止。

（4）下图像我们展示了全部的查找过程：



  2、Kruscal算法

    算法思想描述：先对所有的边进行排序。然后遍历所有的边，将该边所连接的点并入到同一个最下生成树中。

     

    实现（使用了链式前向星）：

  1. /**
  2.  * 链式前向星
  3.  */
  4. struct Edge{
  5. 	int begin;//边的起点
  6. 	int end;//边的终点
  7. 	int weight;//边的权值
  8. 	int selected;//该边是否被选中
  9. }edge[maxm];
  10.  
  11. bool cmp(Edge a,Edge b){
  12. 	if(a.weight != b.weight){
  13. 		return a.weight < b.weight;
  14. 	}
  15.  
  16. 	if(a.begin != b.begin){
  17. 		return a.begin < b.begin;
  18. 	}
  19.  
  20. 	return a.end < b.end;
  21. }
  22.  
  23. int n,m;
  24.  
  25. /**
  26.  * kruscal算法思想:
  27.  * 1)对边排序(贪心思想的体现)
  28.  * 2)遍历每一条边.加入并将该边所连接的点合并到同一颗最小生成树中
  29.  */
  30. int kruscal(){
  31. 	int sum = 0;
  32.  
  33. 	int k = 0;
  34. 	sort(edge+1,edge+1+m,cmp);//对边排序...这是kruscal中使用了贪心思想的体现
  35.  
  36. 	int i;
  37. 	for(i = 1 ; i <= n ; ++i){
  38. 		father[i] = i;
  39. 	}
  40.  
  41. 	for(i = 1 ; i <= m ; ++i){//i在这里是一个计数器..
  42. 		if(k == n-1){//如果合并了n-1条边,说明最下生成树已经生成,可以返回了
  43. 			break;
  44. 		}
  45.  
  46. 		/**
  47. 		 * 判断两个点是否已经在最小生成树里面了,如果不在,则将她们合并到最小哦啊生成树中
  48. 		 */
  49. 		int x = find(edge[i].begin);
  50. 		int y = find(edge[i].end);
  51. 		if(x != y){
  52. 			merge(x,y);
  53. 			k++;//已经合并的边数+1
  54. 			edge[i].selected = true;//将改变标记为选中状态
  55. 			sum += edge[i].weight;//累加最小生成树的边权值
  56. 		}
  57. 	}
  58.  
  59. 	return sum;
  60. }

    时间复杂度：O(mlgm + m),一部分时间花在边排序上面了。。。

     

Ex:

  


需要注意的是使用kruscal算法来解决最小生成树的问题时,输入数据的处理方式。

1）当以边的形式给出图的信息的时候，可以直接往edge[i]里面存。如下所示：

  1. for(i = 1 ; i <= m ; ++i){
  2. 			scanf("%d%d%d",&edge[i].begin,&edge[i].end,&edge[i].weight);
  3.  
  4. 			edge[i].selected = false;
  5. 		}



2）当以矩阵的形式给出图的信息的时候。这是可以现网map[][]矩阵里面存，然后再从里面取,如下所示：

  1. int i;
  2. 		int j;
  3. 		for(i = 1 ; i <= n ; ++i){
  4. 			for(j = 1 ; j <= n ; ++j){
  5. 				scanf("%d",&map[i][j]);
  6. 			}
  7. 		}
  8.  
  9.  
  10. 		for(i = 1 ; i <= n ; ++i){
  11. 			for(j = 1 ; j <= n ; ++j){
  12. 				edge[m].begin = i;
  13. 				edge[m].end = j;
  14. 				edge[m].weight = map[i][j];
  15. 				edge[m++].selected = false;
  16. 			}
  17. 		}
  18. 		m -= 1;//这里的处理很重要,如果不加上这个很可能WA。



有的同学可能会觉得求最小生成树的基本条件和求最短路径的基本条件很像。。。是的。。。

求最短路径的算法主要有：dijkstra、floyd、bellman-ford、SPFA.这些算法的基本条件是：

点数、边数、起点、终点、边的信息


求最小生成树的算法主要有：prim、kruscal。这些算法的基本条件是：

点数、边数、边的信息。这比求最短路径所需要的基本条件少了两个(起点、终点)，其实这也很好理解。因为最小生成树求的是让n个点连通的最小费用。而最短路径算法求的是某一个点到另外一个点的最短路径



例题：

1、NYOJ 38 

      题目与分析：


1》这一道题中，抽象一下为：“给出点数、边数、各边的权值”，求“该无向图的最小生成树”..这道题可以使用Prim算法来解决。和最小生成树裸题有点不同的是，他还在最后加了一种“链接外界”的情况。这时候，只需要在求出最小生成树后，将“外界情况”中耗费最下的那个值加上即可。。

2》题目中有2个很重要的条件：

1、把所有的楼都供上电。（让n个点连通）
2、所用电线花费最少。（费用最小）

-----》合起来就是求让n个点连通的最小费用-----》用最小生成树求解。。。。



1）使用Prim算法解决

  1. /*
  2.  * NYOJ_38.cpp
  3.  *
  4.  *  Created on: 2014年6月9日
  5.  *      Author: Administrator
  6.  */
  7. #include <iostream>
  8. #include <cstdio>
  9.  
  10. using namespace std;
  11.  
  12. const int maxn = 505;
  13. const int maxm = maxn * maxn / 2;
  14. const int inf = 100000004;
  15.  
  16. /**
  17.  * prim算法的基本结构
  18.  */
  19. int map[maxn][maxn];//map[i][j]: 表示i到j这条边的距离
  20. int p[maxn];//p[i]: 表示idian是否在Va集合(最小生成树的集合)中
  21. int dis[maxn];//最小生成树中包含节点i最短边的权值
  22. int pre[maxn];//最小生成树中包含节点i的最短边
  23.  
  24. int n, m;
  25.  
  26. /**
  27.  * 使用prim算法生成无向图的最小生成树
  28.  */
  29. int prim() {
  30. 	int sum = 0;
  31.  
  32. 	int i;
  33. 	for (i = 2; i <= n; ++i) {//初始化
  34. 		p[i] = false;//所有的点(除1外,默认使用1作为起始点)都不在Va集合中
  35. 		dis[i] = map[1][i];
  36. 		pre[i] = 1;
  37. 	}
  38.  
  39. 	dis[1] = 0;
  40. 	p[1] = true;
  41.  
  42. 	for (i = 1; i <= n - 1; ++i) {//循环n-1次，每次加入一个点
  43. 		int min = inf;
  44. 		int k = 0;
  45.  
  46. 		int j;
  47. 		for (j = 1; j <= n; ++j) {//求出边权值最小的那个点
  48. 			if (!p[j] && dis[j] < min) {
  49. 				min = dis[j];
  50. 				k = j;
  51. 			}
  52. 		}
  53.  
  54. 		if(k == 0){//没有电可以拓展,图G不连通
  55. 			return -10;
  56. 		}
  57.  
  58. 		sum += dis[k];
  59.  
  60. 		p[k] = true;//将点k加入到最小生成树中
  61.  
  62. 		for (j = 1; j <= n; ++j) {
  63. 			if (!p[j] && dis[j] > map[k][j]) {
  64. 				dis[j] = map[k][j];
  65. 				pre[j] = k;
  66. 			}
  67. 		}
  68. 	}
  69.  
  70. 	return sum;
  71. }
  72.  
  73. void printDis(){
  74. 	int i;
  75. 	printf("%d %d %d %d\n",dis[1],dis[2],dis[3],dis[4]);
  76.  
  77. 	for(i = 1 ; i <= n ; ++i){
  78. 		printf("%d ",dis[i]);
  79. 	}
  80. 	printf("\n");
  81.  
  82. }
  83.  
  84. int main() {
  85. 	int t;
  86. 	scanf("%d", &t);
  87. 	while (t--) {
  88. 		scanf("%d%d", &n, &m);
  89.  
  90. 		int i, j;
  91. 		for (i = 1; i <= n; ++i) {
  92. 			for (j = 1; j <= n; ++j) {
  93. 				if(i == j){
  94. 					map[i][j] = 0;
  95. 				}else{
  96. 					map[i][j] = inf;
  97. 				}
  98. 			}
  99. 		}
  100.  
  101. 		for (i = 1; i <= m; ++i) {
  102. 			int a, b, c;
  103. 			scanf("%d%d%d", &a, &b, &c);
  104.  
  105. 			if (map[a][b] > c) {//用来处理重边的情况
  106. 				map[a][b] = map[b][a] = c;
  107. 			}
  108.  
  109. 		}
  110.  
  111. 		int sum = prim();
  112.  
  113.  
  114. //		printf("n:%d,m:%d\n",n,m);
  115. //		printDis();
  116.  
  117. 		int mm = inf;
  118.  
  119. 		for (i = 1; i <= n; ++i) {
  120. 			int a;
  121. 			scanf("%d", &a);
  122.  
  123. 			if (mm > a) {
  124. 				mm = a;
  125. 			}
  126. 		}
  127.  
  128. 		printf("%d\n", sum+mm);
  129. 	}
  130.  
  131. 	return 0;
  132. }


以下是再次做这道题时的代码：

  1. /*
  2.  * NY_38.cpp
  3.  *
  4.  *  Created on: 2014年9月7日
  5.  *      Author: pc
  6.  */
  7.  
  8.  
  9. #include <iostream>
  10. #include <cstdio>
  11.  
  12. using namespace std;
  13.  
  14.  
  15. const int maxn = 505;
  16. const int inf = 999999;
  17.  
  18. int s[maxn];
  19. int dis[maxn];
  20. int map[maxn][maxn];
  21.  
  22. int n,m;
  23.  
  24. void initial(){
  25. 	int i;
  26. 	int j;
  27. 	for(i =1 ; i <= n ; ++i){
  28. 		for(j = 1 ; j <= n ; ++j){
  29. 			if(i == j){
  30. 				map[i][j] = 0;
  31. 			}else{
  32. 				map[i][j] = inf;
  33. 			}
  34. 		}
  35. 	}
  36. }
  37.  
  38. int prim(){
  39. 	int sum = 0;
  40.  
  41. 	int i;
  42. 	int j;
  43.  
  44. 	for(i = 1 ; i <= n ; ++i){
  45. 		s[i] = false;
  46. 		dis[i] = map[1][i];
  47. 	}
  48.  
  49. 	s[1] = true;
  50. 	dis[1] = 0;
  51.  
  52. 	for(i = 1 ; i < n ; ++i){
  53. 		int min = inf;
  54. 		int pos;
  55.  
  56. 		for(j = 1 ; j <= n ; ++j){
  57. 			if(!s[j] && min > dis[j]){
  58. 				min = dis[j];
  59. 				pos = j;
  60. 			}
  61. 		}
  62.  
  63. 		s[pos] = true;
  64.  
  65. 		sum += dis[pos];
  66.  
  67. 		for(j = 1 ; j <= n ; ++j){
  68. 			if(!s[j] && dis[j] > map[pos][j]){
  69. 				dis[j] = map[pos][j];
  70. 			}
  71. 		}
  72. 	}
  73.  
  74. 	return sum;
  75. }
  76.  
  77.  
  78. int main(){
  79. 	int t;
  80. 	scanf("%d",&t);
  81.  
  82. 	while(t--){
  83.  
  84. 		scanf("%d%d",&n,&m);
  85. 		initial();
  86.  
  87. 		int i;
  88. 		for(i = 1 ; i <= m ;++i){
  89. 			int a,b,c;
  90. 			scanf("%d%d%d",&a,&b,&c);
  91.  
  92. 			if(map[a][b] > c){
  93. 				map[a][b] = map[b][a] = c;
  94. 			}
  95. 		}
  96.  
  97. 		int min = inf;
  98. 		for(i = 0 ; i < n ; ++i){
  99. 			int a;
  100. 			scanf("%d",&a);
  101. 			if(min > a){
  102. 				min = a;
  103. 			}
  104. 		}
  105.  
  106. 		int sum = prim();
  107.  
  108. 		printf("%d\n",sum+min);
  109. 	}
  110.  
  111. 	return 0;
  112. }




2）使用kruscal算法来解决

         因为这道题的边的范围在500*500=250000之内。因为kruscal算法的时间复杂度是O(m lgm)，所以，还是可以做的。在使用kruscal算法来解决这道题的时候，有一点需要提醒一下的是：当题目以边的形式给出图的信息(而不是以一个邻接矩阵)的时候，这时候我们其实可以不需要邻接矩阵。这时候不需要担心重边的问题，链式前向星能够解决这个问题。

  1. /*
  2.  * NYOJ_38_kruscal.cpp
  3.  *
  4.  *  Created on: 2014年6月11日
  5.  *      Author: Administrator
  6.  */
  7.  
  8. #include <iostream>
  9. #include <cstdio>
  10. #include <algorithm>
  11.  
  12. using namespace std;
  13.  
  14.  
  15. const int maxn = 505;
  16. const int maxm = maxn*maxn;
  17. const int inf = 99999999;
  18.  
  19.  
  20. //在i边的形式给出图的信息的时,如果使用kruscal来解决的话，
  21. //那么其实可以不需要用到邻接矩阵.直接往里面存就行了.因为链式前向星能够处理过重边的问题.
  22. //int map[maxn][maxn];
  23. int father[maxn];
  24. int find(int x) {
  25. 	if (x == father[x]) {
  26. 		return x;
  27. 	}
  28.  
  29. 	father[x] = find(father[x]);
  30. 	return father[x];
  31. }
  32.  
  33. void merge(int x, int y) {
  34. 	int fx = find(x);
  35. 	int fy = find(y);
  36.  
  37. 	if (fx != fy) {
  38. 		father[fx] = fy;
  39. 	}
  40. }
  41.  
  42.  
  43. struct Edge{
  44. 	int begin;
  45. 	int end;
  46. 	int weight;
  47. 	int selected;
  48. }edge[maxm];
  49.  
  50. bool cmp(Edge a,Edge b){
  51. 	if(a.weight != b.weight){
  52. 		return a.weight < b.weight;
  53. 	}
  54.  
  55. 	if(a.begin != b.begin){
  56. 		return a.begin < b.begin;
  57. 	}
  58.  
  59. 	return a.end < b.end;
  60. }
  61.  
  62. int n,m;
  63.  
  64. int kruscal(){
  65. 	int sum = 0;
  66.  
  67. 	int i;
  68. 	for(i = 1 ; i <= n ; ++i){
  69. 		father[i] = i;
  70. 	}
  71.  
  72. 	sort(edge+1,edge+1+m,cmp);
  73.  
  74. 	int k = 0;
  75. 	for(i = 1 ; i <= m ; ++i){
  76. 		if(k == n-1){
  77. 			break;
  78. 		}
  79.  
  80. 		int x = find(edge[i].begin);
  81. 		int y = find(edge[i].end);
  82. 		if(x != y){
  83. 			merge(x,y);
  84. 			k++;
  85. 			edge[i].selected = true;
  86.  
  87. 			sum += edge[i].weight;
  88. 		}
  89.  
  90. 	}
  91.  
  92. 	return sum;
  93. }
  94.  
  95.  
  96. int main(){
  97. 	int t;
  98. 	scanf("%d",&t);
  99. 	while(t--){
  100. 		scanf("%d%d",&n,&m);
  101.  
  102. 		int i;
  103. 		int j;
  104.  
  105. 		for(i = 1 ; i <= m ; ++i){
  106. 			int a,b,c;
  107. 			scanf("%d%d%d",&edge[i].begin,&edge[i].end,&edge[i].weight);
  108. 			edge[i].selected = false;
  109. 		}
  110.  
  111.  
  112. 		int result = kruscal();
  113.  
  114. 		int mina = inf;
  115. 		for(i = 1 ; i <= n ; ++i){
  116. 			int a;
  117. 			scanf("%d",&a);
  118.  
  119. 			if(mina > a){
  120. 				mina = a;
  121. 			}
  122. 		}
  123.  
  124. 		printf("%d\n",result+mina);
  125. 	}
  126.  
  127. 	return 0;
  128. }







  2、山东理工大学OJ 2144

题目与分析：

这道题抽象一下还是；“给出点数、边数、各边的情况，求将所有点连接起来的最短路径的边权和”。这道题可以使用Prim算法来做。。

1）使用Prim算法解决

  1. /*
  2.  * SDOJ_2144.cpp
  3.  *
  4.  *  Created on: 2014年6月10日
  5.  *      Author: Administrator
  6.  */
  7.  
  8. #include <iostream>
  9. #include <cstdio>
  10.  
  11. using namespace std;
  12.  
  13. const int maxn = 105;
  14. const int inf = 9999999;
  15.  
  16. int map[maxn][maxn];
  17. int p[maxn];
  18. int dis[maxn];
  19. int pre[maxn];
  20.  
  21. int n,m;
  22.  
  23. int prim(){
  24. 	int sum = 0;
  25.  
  26. 	int i;
  27. 	for(i = 2 ; i <= n ; ++i){
  28. 		p[i] = false;
  29. 		dis[i] = map[1][i];
  30. 		pre[i] = 1;
  31. 	}
  32.  
  33. 	dis[1] = 0;
  34. 	p[1] = true;
  35.  
  36. 	for(i = 1 ; i <= n-1 ; ++i){//注意,这里不要写成i<=n，因为只需要处理n-1个点(起始点已经处理了)
  37. 		int min = inf;
  38. 		int k = 0;
  39.  
  40. 		int j;
  41. 		for(j = 1 ; j <= n ; ++j){
  42. 			if(!p[j] && dis[j] < min){
  43. 				min = dis[j];
  44. 				k = j;
  45. 			}
  46. 		}
  47.  
  48. 		if(k == 0){
  49. 			return -10;
  50. 		}
  51.  
  52. 		p[k] = true;
  53. 		sum += dis[k];
  54.  
  55.  
  56. 		for(j = 1 ; j <= n ; ++j){
  57. 			if(!p[j] && dis[j] > map[k][j]){
  58. 				dis[j] = map[k][j];
  59. 				pre[j] = k;
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. 	return sum;
  65. }
  66.  
  67.  
  68. int main(){
  69. 	while(scanf("%d%d",&n,&m)!=EOF){
  70. 		int i,j;
  71. 		for(i = 1 ; i <= n ; ++i){
  72. 			for(j = 1 ; j <= n ; ++j){
  73. 				if(i == j){
  74. 					map[i][j] = 0;
  75. 				}else{
  76. 					map[i][j] = inf;
  77. 				}
  78. 			}
  79. 		}
  80.  
  81. 		for(i = 1 ; i <= m ; ++i){
  82. 			int a,b,c;
  83. 			scanf("%d%d%d",&a,&b,&c);
  84.  
  85. 			if(map[a][b] > c){
  86. 				map[a][b] = map[b][a] = c;
  87. 			}
  88. 		}
  89.  
  90. 		int sum = prim();
  91.  
  92. 		printf("%d\n",sum);
  93. 	}
  94.  
  95. 	return 0;
  96. }
  97.  
  98.


2）使用kruscal算法来解决

  1. /*
  2.  * SDOJ_2144_kruscal.cpp
  3.  *
  4.  *  Created on: 2014年6月11日
  5.  *      Author: Administrator
  6.  */
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10.  
  11. using namespace std;
  12.  
  13.  
  14. const int maxn = 105;
  15. const int maxm = maxn*maxn;
  16. const int inf = 9999999;
  17.  
  18. int map[maxn][maxn];
  19. int father[maxn];
  20. int find(int x) {
  21. 	if (x == father[x]) {
  22. 		return x;
  23. 	}
  24.  
  25. 	father[x] = find(father[x]);
  26. 	return father[x];
  27. }
  28.  
  29. void merge(int x, int y) {
  30. 	int fx = find(x);
  31. 	int fy = find(y);
  32.  
  33. 	if (fx != fy) {
  34. 		father[fx] = fy;
  35. 	}
  36. }
  37.  
  38. struct Edge{
  39. 	int begin;
  40. 	int end;
  41. 	int weight;
  42. 	int selected;
  43. }edge[maxm];
  44.  
  45. bool cmp(Edge a,Edge b){
  46. 	if(a.weight != b.weight){
  47. 		return a.weight < b.weight;
  48. 	}
  49.  
  50. 	if(a.begin < b.begin){
  51. 		return a.begin < b.begin;
  52. 	}
  53.  
  54. 	return a.end < b.end;
  55. }
  56.  
  57. int n,m;
  58.  
  59. int kruscal(){
  60. 	int sum = 0;
  61.  
  62. 	int i;
  63. 	for(i = 1 ; i <= n ; ++i){
  64. 		father[i] = i;
  65. 	}
  66.  
  67. 	sort(edge+1,edge+1+m,cmp);
  68.  
  69. 	int k = 0;
  70. 	for(i = 1 ; i <= m ; ++i){
  71. 		if(k == n-1){
  72. 			break;
  73. 		}
  74.  
  75. 		int x = find(edge[i].begin);
  76. 		int y = find(edge[i].end);
  77. 		if(x != y){
  78. 			merge(x,y);
  79. 			k++;
  80. 			edge[i].selected = true;
  81.  
  82. 			sum += edge[i].weight;
  83. 		}
  84. 	}
  85.  
  86. 	return sum;
  87. }
  88.  
  89.  
  90. int main(){
  91. 	while(scanf("%d%d",&n,&m)!=EOF){
  92. 		int i;
  93. 		for(i = 1 ; i <= m ; ++i){
  94. 			scanf("%d%d%d",&edge[i].begin,&edge[i].end,&edge[i].weight);
  95.  
  96. 			edge[i].selected = false;
  97. 		}
  98.  
  99. 		int result = kruscal();
  100.  
  101. 		printf("%d\n",result);
  102. 	}
  103.  
  104. 	return 0;
  105. }
  106.



3、HDU 1102

题目与分析：

这一道题抽象一下，还是求图的最小边权和的最小生成树问题。这一道题与最裸的最下生成树问题的差别主要由以下几点：

1）之前是以边的形式给出图的信息。这道题是一矩阵的形式给出了整张图的信息

2）引入了“已修建道路的概念”。对于“已修建道路”，我们可以理解为：修建这条道路是费用为0即可。


方法一：Prim算法解决无向图的最小生成树问题

  1. /*
  2.  * HDU_1102.cpp
  3.  *
  4.  *  Created on: 2014年6月10日
  5.  *      Author: Administrator
  6.  */
  7.  
  8. #include <iostream>
  9. #include <cstdio>
  10.  
  11. using namespace std;
  12.  
  13. const int maxn = 105;
  14. const int inf = 9999999;
  15.  
  16. int map[maxn][maxn];
  17. int p[maxn];
  18. int dis[maxn];
  19. int pre[maxn];
  20.  
  21. int n, m;
  22.  
  23. int prim() {
  24. 	int sum = 0;
  25.  
  26. 	int i;
  27. 	for (i = 2; i <= n; ++i) {
  28. 		p[i] = false;
  29. 		dis[i] = map[1][i];
  30. 		pre[i] = 1;
  31. 	}
  32.  
  33. 	dis[1] = 0;
  34. 	p[1] = true;
  35.  
  36. 	for (i = 1; i <= n - 1; ++i) {
  37. 		int min = inf;
  38. 		int k = 0;
  39.  
  40. 		int j;
  41. 		for (j = 1; j <= n; ++j) {
  42. 			if (!p[j] && dis[j] < min) {
  43. 				min = dis[j];
  44. 				k = j;
  45. 			}
  46. 		}
  47.  
  48. 		if (k == 0) {
  49. 			return -10;
  50. 		}
  51.  
  52. 		p[k] = true;
  53. 		sum += dis[k];
  54.  
  55. 		for (j = 1; j <= n; ++j) {
  56. 			if (!p[j] && dis[j] > map[k][j]) {
  57. 				dis[j] = map[k][j];
  58. 				pre[j] = k;
  59. 			}
  60. 		}
  61. 	}
  62.  
  63. 	return sum;
  64. }
  65.  
  66. int main() {
  67. 	while (scanf("%d", &n) != EOF) {
  68. 		int i, j;
  69. 		for (i = 1; i <= n; ++i) {
  70. 			for (j = 1; j <= n; ++j) {
  71. 				scanf("%d", &map[i][j]);
  72. 			}
  73. 		}
  74.  
  75. 		scanf("%d", &m);
  76. 		for (i = 1; i <= m; ++i) {
  77. 			int a, b;
  78. 			scanf("%d%d", &a, &b);
  79. 			map[a][b] = map[b][a] = 0;
  80. 		}
  81.  
  82. 		int sum = prim();
  83.  
  84. 		printf("%d\n", sum);
  85. 	}
  86.  
  87. 	return 0;
  88. }



4、HDU 1233

题目与分析：

     这道题其实与最裸的最下生成树问题没有太大的区别。都是给出点数、和以边的形式给出图的信息。如果说有区别的话，那便是，之前是随机给定边数，现在是有一个公式给定边数。

1）使用Prim算法解决

  1. /*
  2.  * HDU_1233.cpp
  3.  *
  4.  *  Created on: 2014年6月10日
  5.  *      Author: Administrator
  6.  */
  7.  
  8.  
  9. #include <iostream>
  10. #include <cstdio>
  11.  
  12. using namespace std;
  13.  
  14. const int maxn = 105;
  15. const int inf = 9999999;
  16.  
  17. int map[maxn][maxn];
  18. int p[maxn];
  19. int dis[maxn];
  20. int pre[maxn];
  21.  
  22. int n,m;
  23.  
  24. int prim(){
  25. 	int sum = 0;
  26.  
  27. 	int i;
  28. 	for(i = 2 ; i <= n ; ++i){
  29. 		p[i] = false;
  30. 		dis[i] = map[1][i];
  31. 		pre[i] = 1;
  32. 	}
  33.  
  34. 	dis[1] = 0;
  35. 	p[1] = true;
  36.  
  37. 	for(i = 1 ; i <= n-1 ; ++i){
  38. 		int min = inf;
  39. 		int k = 0;
  40.  
  41. 		int j;
  42. 		for(j = 1 ; j <= n ; ++j){
  43. 			if(!p[j] && dis[j] < min){
  44. 				min = dis[j];
  45. 				k = j;
  46. 			}
  47. 		}
  48.  
  49. 		if(k == 0){
  50. 			return -10;
  51. 		}
  52.  
  53. 		p[k] = true;
  54.  
  55. 		sum += dis[k];
  56.  
  57. 		for(j = 1 ; j <= n ; ++j){
  58. 			if(!p[j] && dis[j] > map[k][j]){
  59. 				dis[j] = map[k][j];
  60. 				pre[j] = k;
  61. 			}
  62. 		}
  63. 	}
  64.  
  65. 	return sum;
  66. }
  67.  
  68. int main(){
  69. 	while(scanf("%d",&n),n!=0){
  70.  
  71.  
  72. 		m = n*(n-1)/2;
  73.  
  74. 		int i;
  75. 		int j;
  76. 		for(i = 1 ; i <= n ; ++i){
  77. 			for(j = 1 ; j <= n ; ++j){
  78. 				if(i == j){
  79. 					map[i][j] = 0;
  80. 				}else{
  81. 					map[i][j] = inf;
  82. 				}
  83. 			}
  84. 		}
  85.  
  86. 		for(i = 1 ; i <= m ; ++i){
  87. 			int a,b,c;
  88. 			scanf("%d%d%d",&a,&b,&c);
  89.  
  90. 			if(map[a][b] > c){
  91. 				map[a][b] = map[b][a] = c;
  92. 			}
  93. 		}
  94.  
  95. 		int sum = prim();
  96.  
  97. 		printf("%d\n",sum);
  98. 	}
  99.  
  100. 	return 0;
  101. }
  102.


2）使用kruscal算法来解决

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int maxn = 105;
  8. const int maxm = maxn*maxn;
  9.  
  10. int map[maxn][maxn];
  11. int father[maxn];
  12. int find(int x) {
  13. 	if (x == father[x]) {
  14. 		return x;
  15. 	}
  16.  
  17. 	father[x] = find(father[x]);
  18. 	return father[x];
  19. }
  20.  
  21. void merge(int x, int y) {
  22. 	int fx = find(x);
  23. 	int fy = find(y);
  24.  
  25. 	if (fx != fy) {
  26. 		father[fx] = fy;
  27. 	}
  28. }
  29.  
  30.  
  31. struct Edge{
  32. 	int begin;
  33. 	int end;
  34. 	int weight;
  35. 	int selected;
  36. }edge[maxm];
  37.  
  38. bool cmp(Edge a, Edge b){
  39. 	if(a.weight != b.weight){
  40. 		return a.weight < b.weight;
  41. 	}
  42.  
  43. 	if(a.begin != b.begin){
  44. 		return a.begin < b.begin;
  45. 	}
  46.  
  47. 	return a.end < b.end;
  48. }
  49.  
  50. int n,m;
  51.  
  52. int kruscal(){
  53. 	int sum = 0;
  54.  
  55. 	int i;
  56. 	for( i = 1 ; i <= n ; ++i){
  57. 		father[i] = i;
  58. 	}
  59.  
  60. 	sort(edge+1,edge+1+m,cmp);
  61.  
  62. 	int k = 0;
  63. 	for(i = 1 ; i <= m ; ++i){
  64. 		if(k == n-1){
  65. 			break;
  66. 		}
  67.  
  68. 		int x = find(edge[i].begin);
  69. 		int y = find(edge[i].end);
  70. 		if(x != y){
  71. 			merge(x,y);
  72. 			k++;
  73. 			edge[i].selected = true;
  74.  
  75. 			sum += edge[i].weight;
  76. 		}
  77. 	}
  78.  
  79. 	return sum;
  80. }
  81.  
  82.  
  83. int main(){
  84. 	while(scanf("%d",&n),n){
  85. 		m = n*(n-1)/2;
  86.  
  87. 		int i;
  88. 		for(i = 1 ; i <= m ; ++i){
  89. 			scanf("%d%d%d",&edge[i].begin,&edge[i].end,&edge[i].weight);
  90. 			edge[i].selected = false;
  91. 		}
  92.  
  93. 		int result = kruscal();
  94.  
  95. 		printf("%d\n",result);
  96. 	}
  97.  
  98. 	return 0;
  99. }



5、POJ 1258

题目与分析：

       这道题的数据的给出的形式其实上面已经分析过了。“给出点数、以邻接矩阵的形式给出图的信息。求将所有点连接起来的最小边权值之和”。


2）使用kruscal算法来解决

  1. /*
  2.  * POJ_1258.cpp
  3.  *
  4.  *  Created on: 2014年6月10日
  5.  *      Author: Administrator
  6.  */
  7.  
  8. #include <iostream>
  9. #include <cstdio>
  10. #include <algorithm>
  11.  
  12. using namespace std;
  13.  
  14. const int maxn = 105;
  15. const int maxm = maxn*maxn;
  16.  
  17. /**
  18.  * 并查集的基本结构
  19.  */
  20. int map[maxn][maxn];
  21. int father[maxn];
  22. int find(int x) {
  23. 	if (x == father[x]) {
  24. 		return x;
  25. 	}
  26.  
  27. 	father[x] = find(father[x]);
  28. 	return father[x];
  29. }
  30.  
  31. void merge(int x, int y) {
  32. 	int fx = find(x);
  33. 	int fy = find(y);
  34.  
  35. 	if (fx != fy) {
  36. 		father[fx] = fy;
  37. 	}
  38. }
  39.  
  40. /**
  41.  * 链式前向星
  42.  */
  43. struct Edge{
  44. 	int begin;
  45. 	int end;
  46. 	int weight;
  47. 	int selected;
  48. }edge[maxm];
  49.  
  50. bool cmp(Edge a,Edge b){
  51. 	if(a.weight != b.weight){
  52. 		return a.weight < b.weight;
  53. 	}
  54.  
  55. 	if(a.begin != b.begin){
  56. 		return a.begin < b.begin;
  57. 	}
  58.  
  59. 	return a.end < b.end;
  60. }
  61.  
  62. int n,m;
  63.  
  64. /**
  65.  * kruscal算法思想:
  66.  * 1)对边排序(贪心思想的体现)
  67.  * 2)遍历每一条边.加入并将该边所连接的点合并到同一颗最小生成树中
  68.  */
  69. int kruscal(){
  70. 	int sum = 0;
  71.  
  72. 	int k = 0;
  73. 	sort(edge+1,edge+1+m,cmp);//对边排序...这是kruscal中使用了贪心思想的体现
  74.  
  75. 	int i;
  76. 	for(i = 1 ; i <= n ; ++i){
  77. 		father[i] = i;
  78. 	}
  79.  
  80. 	for(i = 1 ; i <= m ; ++i){//i在这里是一个计数器..
  81. 		if(k == n-1){//如果合并了n-1条边,说明最下生成树已经生成,可以返回了
  82. 			break;
  83. 		}
  84.  
  85. 		/**
  86. 		 * 判断两个点是否已经在最小生成树里面了,如果不在,则将她们合并到最小哦啊生成树中
  87. 		 */
  88. 		int x = find(edge[i].begin);
  89. 		int y = find(edge[i].end);
  90. 		if(x != y){
  91. 			merge(x,y);
  92. 			k++;//已经合并的边数+1
  93. 			edge[i].selected = true;//将改变标记为选中状态
  94. 			sum += edge[i].weight;//累加最小生成树的边权值
  95. 		}
  96. 	}
  97.  
  98. 	return sum;
  99. }
  100.  
  101. int main(){
  102. 	while(scanf("%d",&n)!=EOF){
  103. 		m = 1;
  104.  
  105. 		int i;
  106. 		int j;
  107. 		for(i = 1 ; i <= n ; ++i){
  108. 			for(j = 1 ; j <= n ; ++j){
  109. 				scanf("%d",&map[i][j]);
  110. 			}
  111. 		}
  112.  
  113.  
  114. 		for(i = 1 ; i <= n ; ++i){
  115. 			for(j = 1 ; j <= n ; ++j){
  116. 				edge[m].begin = i;
  117. 				edge[m].end = j;
  118. 				edge[m].weight = map[i][j];
  119. 				edge[m++].selected = false;
  120. 			}
  121. 		}
  122. 		m -= 1;//这里的处理很重要,如果不加上这个很可能WA。
  123.  
  124. 		int result = kruscal();
  125.  
  126. 		printf("%d\n",result);
  127. 	}
  128.  
  129. 	return 0;
  130. }







      



      

   




声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/788816
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号