> #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 ，咋超时了呢，那位大牛有空看一下 (32) gaifangyu 2012-02-12 15:26:00