| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:刚会用prim ,咋超时了呢,那位大牛有空看一下In Reply To:刚会用prim ,咋超时了呢,那位大牛有空看一下 Posted by:lxmacm at 2010-12-06 22:08:15 while(scanf("%d",&N)&&N!=0)错了
> #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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator