题目：hdoj-1233

题解：

本题是典型的最小生成树问题，给出的是无向图，这里使用的方法是Prim最小生成树算法。

Reference

Prim算法参照：最小生成树-Prim算法和Kruskal算法，讲的很详细了。

测试的时候可以参考这幅图：

算法介绍：

主要步骤(摘自上文链接)：

1).输入：一个加权连通图，其中顶点集合为V，边集合为E；

2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；

3).重复下列操作，直到Vnew = V：

a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。

本题维护两个数组：

(1)Primgh二维数组，存储图。

(2)refer数组，判断一个节点是否在Vnew中。

用于存边的数组Enew在本题中不需要。

代码：

//

//  main.cpp

//  Prim_1233

//

//  Created by wasdns on 16/11/24.

//  Copyright © 2016年 wasdns. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <string>

#include <string.h>

#define maxn 10000005;

using namespace std;

int Primgh[10000][10000];                        //存储图

bool refer[10005];                               //判断是否在Enew中

/*

    用于初始化的函数

 */

void Initial(int n, int m)

{

    int i, j;

    for (i = 1; i <= n; i++)

    {

        refer[i] = false;

        for (j = 1; j <= n; j++)

        {

            if (i == j) {

                Primgh[i][j] = 0;

            }

            else Primgh[i][j] = maxn;

        }

    }

    int u, v, w;

    for (i = 1; i <= m; i++)

    {

        cin >> u >> v >> w;

        Primgh[u][v] = w;

        Primgh[v][u] = w;

    }

}

/*

    Prim算法，主体部分

 */

int Prim_Alg(int n, int m)

{

    Initial(n, m);

    int i, j, k;

    int ans = 0;

    //最小生成树的路径长度                 

    refer[1] = true;

    //选择点1出发        

    //最小生成树一共有n-1条边，因此需要寻找最短边n-1次，基于贪心

    for (i = 1; i <= n-1; i++)

    {

        int minlen = maxn;

        //minlen: 在Vnew中的节点所连接的边中，寻找cost最小的边

        int rcd = 1;

        //cost最小的边有两个节点，rcd记录其中的不属于Vnew的节点

        for (j = 1; j <= n; j++)

        {

            if (!refer[j]) continue;

            //遍历Vnew中的所有节点

            int len1 = maxn;

            //对于Vnew中的某个节点来说，所连接的最短的路径cost大小

            int rcd1 = 1;

            //对于Vnew中的某个节点来说，rcd记录的节点

            //贪心，寻找这个节点连接的cost最小的路径

            for (k = 1; k <= n; k++)

            {

                if (!refer[k])

                {

                    if (Primgh[j][k] < len1) {

                        len1 = Primgh[j][k];

                        rcd1 = k;

                    }

                }

            }

            if (len1 < minlen) {

                //判断贪心得到的路径是否是全局cost最短

                minlen = len1;

                rcd = rcd1;

            }

        }

        /*Debug：*/

        //char check = 'A'+rcd-1;

        //cout << "rcd: " << check << endl;

        //cout << "minlen: " << minlen << endl;

        refer[rcd] = true;

        //贪心求出cost最小的路径，rcd记录的节点入Vnew

        rcd = 1;

        //重置rcd

        ans += minlen;

    }

    return ans;

}

int main()

{

    int n, m;

    while (scanf("%d", &n) != EOF)

    {

        if (n == 0) break;

        m = n * (n-1) / 2;

        cout << Prim_Alg(n, m) << endl;

    }

    return 0;

}

2016/11/24