Prim算法

具体内容观看>>>51NOD
最小生成树的Prim算法也是贪心算法的一大经典应用。Prim算法的特点是时刻维护一棵树，算法不断加边，加的过程始终是一棵树。

Prim算法过程：

一条边一条边地加， 维护一棵树。
初始 $E ＝｛｝$E＝｛｝空集合， $V = ｛$V=｛任意节点$｝$｝
循环 $（n – 1）$（n–1） 次，每次选择一条边$（v1,v2）$（v1,v2）， 满足：$v1$v1 属于 $V , v2$V,v2 不属于 $V$V。且 $（v1,v2）$（v1,v2）权值最小。
$E = E + （v1,v2）$E=E+（v1,v2）
$V = V + v2$V=V+v2
最终 $E$E 中的边是一棵最小生成树， $V$V 包含了全部节点。
最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法;

输入

第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。$（2 &lt;= N &lt;= 1000, 1 &lt;= M &lt;= 50000)$（2<=N<=1000,1<=M<=50000)
第$2 - M + 1$2−M+1行：每行3个数$S$S $E$E $W$W，分别表示M条边的2个顶点及权值。$(1 &lt;= S, E &lt;= N，1 &lt;= W &lt;= 10000)$(1<=S,E<=N，1<=W<=10000)

输出

输出最小生成树的所有边的权值之和。

输入示例

9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

输出示例

37

请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。
不同语言如何处理输入输出，请查看下面的语言说明。
网上搜的一个代码
???? (☄⊙ω⊙)☄

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1005;
bool vis[maxn];
int cost[maxn][maxn], lowc[maxn];
int prim(int cost[][maxn], int n)
{
    int ans = 0;
    memset(vis, false, sizeof(vis));
    vis[0] = true;
    for(int i = 1; i < n; ++i)
        lowc[i] = cost[0][i];
    for(int i = 1; i < n; ++i)
    {
        int minc = INF;
        int p = -1;
        for(int j = 0; j < n; ++j)
        {
            if(!vis[j] && minc > lowc[j])
            {
                minc = lowc[j];
                p = j;
            }
        }
        if(minc == INF)
            return -1;
        ans += minc;
        vis[p] = true;
        for(int j = 0; j < n; ++j)
        {
            if(!vis[j] && lowc[j] > cost[p][j])
                lowc[j] = cost[p][j];
        }
    }
    return ans;
}
int main()
{
    int n, m, u, v, w;   //n是顶点数，m是边数
    scanf("%d %d", &m, &n);
    memset(cost, INF, sizeof(cost));
    //memset(vis, 0 ,sizeof(vis));
    for(int i = 0; i < n; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        cost[u - 1][v - 1] = cost[v - 1][u - 1] = w;
    }
    cout << prim(cost, m) <<endl;
 
    return 0;
}

以下图为例介绍Prim算法的执行过程。

Prim算法的过程从A开始 V = {A}, E = {}

选中边AF , V = {A, F}, E = {(A,F)}

选中边FB, V = {A, F, B}, E = {(A,F), (F,B)}

选中边BD, V = {A, B, F, D}, E = {(A,F), (F,B), (B,D)}

选中边DE, V = {A, B, F, D, E}, E = {(A,F), (F,B), (B,D), (D,E)}

选中边BC, V = {A, B, F, D, E, c}, E = {(A,F), (F,B), (B,D), (D,E), (B,C)}, 算法结束。