Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:刚会用prim ,咋超时了呢,那位大牛有空看一下

Posted by Sue0610 at 2011-07-16 09:47:13 on Problem 1258
In Reply To:刚会用prim ,咋超时了呢,那位大牛有空看一下 Posted by:lxmacm at 2010-12-06 22:08:15
> #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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator