中国大学MOOC-数据结构基础习题集、06-3、公路村村通

题目链接：http://www.patest.cn/contests/mooc-ds/06-3

题目分析：典型最小生成树问题，且只需输出树各边的权值之和出来就可以了。博主这里用的是Prim算法。

特别说明：

　　1. 用邻接矩阵表示图比较容易。保存路径长度就可以了。因为强调了数组下标从1开始，因此在输入完n和m时，先执行一步n++，方便以后为数组申请空间。

　　2. 二维数组的动态申请及初始化，不推荐大家#define一个较大的数，然后直接int a[MAX][MAX]，这样做是十分不负责的，十分浪费空间。如果不会的同学，可以参见如下方法：

 1     // 用邻接矩阵存储图
 2     int **data = new int*[n];
 3     for(int i=0; i<n+1; i++)
 4     {
 5         data[i] = new int[n];
 6     }
 7     // 邻接矩阵初始化
 8     for(int i=0; i<n; i++)
 9     {
10         for(int j=0; j<n; j++)
11         {
12             data[i][j] = MAXNUM;
13         }
14     }

　　3. 求“尚未收集”的dist值最小的函数，参数是dist，collected标记是否被收集，及数组的长度n。注意数组下标从1开始：

 1 int minDist(int dist[], bool collected[], int n)
 2 {
 3     int mindist = MAXNUM;
 4     int icount = NOTEXIST;
 5     for(int i=1; i<n ; i++)
 6     {
 7         if(dist[i] < mindist && collected[i] == false)
 8         {
 9             icount = i;
10             mindist = dist[i];
11         }
12     }
13     return icount;
14 }

　　4. 用#define定义无穷大（100000000）和不存在（-1），避免程序中出现魔数，也方便修改。

1 #define MAXNUM 10000000
2 #define NOTEXIST -1

　　5. 可以用fill函数，对一个数组进行快速初始化，避免写for循环。方法如下：

1 fill(a, a+aLen, 100);    // 数组a长度为aLen，用100填满整个数组

代码分析：

　　普利姆算法：24~71（其中parent数组不设定也可以，这里并没有要求表示树的结构）

　　主函数：72~100（注意输入图的数据时，注意是图是无向图，也就是双向图）

  1 #include <iostream>
  2 #include <stack>
  3 
  4 #define MAXNUM 10000000
  5 #define NOTEXIST -1
  6 
  7 using namespace std;
  8 
  9 int minDist(int dist[], bool collected[], int n)
 10 {
 11     int mindist = MAXNUM;
 12     int icount = NOTEXIST;
 13     for(int i=1; i<n ; i++)
 14     {
 15         if(dist[i] < mindist && collected[i] == false)
 16         {
 17             icount = i;
 18             mindist = dist[i];
 19         }
 20     }
 21     return icount;
 22 }
 23 
 24 int Prim(int *data[], int n, int m)
 25 {
 26     // 集合: 用来存储收集到的结点
 27     stack<int> MST;
 28     MST.push(0);
 29     // dist: 记录长度
 30     int *dist = new int[n];
 31     fill(dist, dist+n, MAXNUM);
 32     dist[1] = 0;
 33     // collected: 标记是否被访问
 34     bool *collected = new bool[n];
 35     fill(collected, collected+n, false);
 36     // parent: 记录树的结构
 37     int *parent = new int[n];
 38     fill(parent, parent+n, NOTEXIST);
 39     // output: 最终结果
 40     int output = 0;
 41     while (1)
 42     {
 43         int V = minDist(dist, collected, n);
 44         if (V == NOTEXIST)
 45             break;
 46         MST.push(V);
 47         output += dist[V];
 48         dist[V] = 0;
 49         collected[V] = true;
 50         for(int W=1; W<n; W++)
 51         {
 52             if(data[V][W] != MAXNUM         // 如果W是V的邻接点
 53                && collected[W] == false     // 如果W没有被访问
 54                && data[V][W] < dist[W])
 55             {
 56                 dist[W] = data[V][W];
 57                 parent[W] = V;
 58             }
 59         }
 60     }
 61     if(MST.size() != n)
 62         return NOTEXIST;
 63     else
 64         return output;
 65 }
 66 /*
 67 dist[V] = E(s,V)或 正无穷
 68 parent[s] = -1（代表根结点）
 69 T = O( |V|2 )
 70 */
 71 
 72 int main()
 73 {
 74     int n, m;
 75     cin >> n >> m;
 76     n++;
 77     // 用邻接矩阵存储图
 78     int **data = new int*[n];
 79     for(int i=0; i<n+1; i++)
 80     {
 81         data[i] = new int[n];
 82     }
 83     // 邻接矩阵初始化
 84     for(int i=0; i<n; i++)
 85     {
 86         for(int j=0; j<n; j++)
 87         {
 88             data[i][j] = MAXNUM;
 89         }
 90     }
 91     for(int i=0; i<m; i++)
 92     {
 93         int a, b, c;
 94         cin >> a >> b >> c;
 95         data[a][b] = c;
 96         data[b][a] = c;
 97     }
 98     cout << Prim(data, n, m) << endl;
 99     return 0;
100 }

AC成果：