#include<stdio.h>

int cost[101][101];
int lowc[101];
int visit[101];

int rec;
int N;
int prim()
{
    int i,j,p;
    int minc;
    rec=0;
//    memset(visit,0, sizeof(visit));

    int inf=100000000;
    for(i=1;i<N;i++)
    {
        visit[i]=0;
        lowc[i]=cost[0][i];
    }
    visit[0]=1;
    for(i=1;i<N;i++)
    {
       minc=inf;p=-1;
       for(j=0;j<N;j++)
        {
            if(visit[j]==0&&minc>lowc[j])
              {
                  minc=lowc[j];
                  p=j;
              }
        }

        if(minc==inf ) return -1;
        rec+=minc;
        visit[p]=1;
        for(j=0;j<N;j++)
         {
             if(visit[j]==0&&lowc[j]>cost[p][j])
                lowc[j]=cost[p][j];
         }
    }
    return rec;
}

int main()
{
    int i,j;
    while(scanf("%d",&N)&&N!=0)
    {
        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++)
            {
                scanf("%d",&cost[i][j]);
            }
            //printf("\n");
        }
       // printf("\n");
        printf("%d\n",prim());
    }
    return 0;
}

• Re:刚会用prim ，咋超时了呢，那位大牛有空看一下 (1256) Sue0610 2011-07-16 09:47:13
  • Re:刚会用prim ，咋超时了呢，那位大牛有空看一下 (32) gaifangyu 2012-02-12 15:26:00
• Re:刚会用prim ，咋超时了呢，那位大牛有空看一下 (1289) zero91 2011-08-18 12:31:08