学步园

题目链接：点

/*
  Date:22.9.2013
  还是畅通工程
  裸的Prim.
  还没有学习Kruscal.明天学习！！
  比较prim和Kruscal的区别.
*/
#include<stdio.h>
#include<string.h>
#define Max 105
#define INF 0xffffff
//一般用三个数组Map邻接矩阵用来存储两个结点之间的权值.
//              Lowcost用来存储和i相连的最小权值.
//              vis(bool)用来存储i是否被链接.
//一般有两个步骤吧！
int Map[Max][Max],Lowcost[Max];
int Prim(int v0,int n)
{
    //第一步:初始化.需要注意的是可以以任意一结点开始.
    bool vis[n];vis[v0]=true;
    for(int i=1;i<=n;i++)
    if(i!=v0)
    {
        Lowcost[i]=Map[v0][i];
        vis[i]=false;
    }
    int Sum=0;
    //第二步:贪心选择.
    for(int i=1;i<=n;i++)
    {
        int temp=INF;
        int t=v0;
        for(int j=1;j<=n;j++)
        if(!vis[j]&&Lowcost[j]<temp)
        {
            temp=Lowcost[j];
            t=j;
        }
        if(t==v0) return Sum;
        Sum+=temp;
        vis[t]=true;
        //Lowcost每次都要更新,Lowcost每次选择时都的最新的数据.
        //即已经选入的点和没选入点最小权值.
        for(int j=1;j<=n;j++)
        if(!vis[j]&&Lowcost[j]>Map[t][j])
        Lowcost[j]=Map[t][j];
    }
}
int main()
{
    int N;
    while(scanf("%d",&N)&&N)
    {
        memset(Map,'a',sizeof(Map));
        int a,b,c;
        for(int i=1;i<=N*(N-1)/2;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            Map[a][b]=c;
            Map[b][a]=c;
        }
        printf("%d\n",Prim(1,N));
    }
}