这是一道求最小生成树的题目。有kruskal算法和prim算法这两种解决最小生成树问题的算法。题意是说有n个点(2<=n<=1000且点的编号从1开始),m个连通方案(1<=m<=15000),并且每个连通方案都有需要消耗电缆的长度。要求从这些连通方案中选取一部分使得所有点都构成一个网络(点与点之间可以有其他的点互相连通。不要构成环,可用并查集实现)并且使所用方案中的最大消耗电缆长度尽量小,然后输出所用方案中最大消耗电缆长度,使用方案数以及每个方案的点的编号。
接下来讲解题思路,输入n和m后依次输入m个连通方案,把连通方案根据消耗电缆长度也就是边的长度按照升序排序,然后遍历方案,当方案中的两个点没有连通(也就是不属于一个集合),那么执行该方案(合并两点)。最后输出方案中的最大电缆消耗长度(也就是最长边),使用方案数和每个方案连通的两个点。这是标准kruskal算法。
注意实际上POJ上的这道题样例是有错误的,可以无视。另外这道题是特殊评测,所以有多种输出方案。
接下来是我的解题代码,kruskal算法:
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define N 1001 4 #define M 15001 5 6 typedef struct /*定义方案结构体*/ 7 { 8 int x; 9 int y; 10 int len; /*消耗电缆长度*/ 11 int flag; /*标志变量,1代表使用该方案*/ 12 }SIDE; 13 14 SIDE side[M]; 15 int bleg[N]; /*存储节点*/ 16 int n, m; 17 18 void ReadSort(); /*输入方案并为方案排序*/ 19 20 int Mycompare(const void *a, const void *b); /*方案的比较函数,qsort函数需要*/ 21 22 int Find(int x); 23 24 void Union(int x, int y); 25 26 void Init(); /*初始化*/ 27 28 int main() 29 { 30 int i; 31 int num = 0; /*记录使用的方案数*/ 32 int len = 0; /*记录方案中消耗的电缆最大长度*/ 33 scanf("%d %d", &n, &m); 34 ReadSort(); 35 Init(); 36 for (i=0; i<m; i++) 37 { 38 if (Find(side[i].x) != Find(side[i].y)) /*如果两点没有连通*/ 39 { 40 len = side[i].len; 41 num++; 42 side[i].flag = 1; 43 Union(side[i].x, side[i].y); 44 } 45 } 46 printf("%d %d ", len, num); 47 for (i=0; i<m; i++) 48 { 49 if (side[i].flag == 1) 50 { 51 printf("%d %d ", side[i].x, side[i].y); 52 } 53 } 54 return 0; 55 } 56 57 void ReadSort() /*输入与排序*/ 58 { 59 int i; 60 for (i=0; i<m; i++) 61 { 62 scanf("%d %d %d", &side[i].x, &side[i].y, &side[i].len); 63 } 64 qsort(side, m, sizeof(SIDE), Mycompare); 65 return; 66 } 67 68 int Mycompare(const void *a, const void *b) /*排序比较函数*/ 69 { 70 SIDE *pa = (SIDE *)a; 71 SIDE *pb = (SIDE *)b; 72 if (pa->len != pb->len) 73 { 74 return (pa->len - pb->len); 75 } 76 else if (pa->x != pb->x) 77 { 78 return (pa->x - pb->x); 79 } 80 return (pa->y - pb->y); 81 } 82 83 void Init() /*初始化函数*/ 84 { 85 int i; 86 for (i=1; i<=n; i++) 87 { 88 bleg[i] = i; 89 } 90 for (i=0; i<m; i++) 91 { 92 side[i].flag = 0; 93 } 94 return; 95 } 96 97 int Find(int x) /*查找根节点*/ 98 { 99 int y = bleg[x]; 100 int z; 101 while (y != bleg[y]) 102 { 103 y = bleg[y]; 104 } 105 while (x != bleg[x]) /*路径压缩*/ 106 { 107 z = bleg[x]; 108 bleg[x] = y; 109 x = z; 110 } 111 return y; 112 } 113 114 void Union(int x, int y) /*合并操作*/ 115 { 116 int fx = Find(x); 117 int fy = Find(y); 118 bleg[fx] = fy; 119 return; 120 }