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

## Re:为什么WA啊 大牛给看看

Posted by singlelove at 2007-04-09 20:55:31 on Problem 3107
In Reply To:为什么WA啊 大牛给看看 Posted by:xia192041 at 2006-11-23 14:50:34
```> #include<stdio.h>
> #include<stdlib.h>
> #include<string.h>
>
> struct In
> {
> int x;
> int y;
> }s[50001];
>
> int flag[50001],num[50001],t;
> int search(int n)
> {
>     int max,sum,i,temp;
>     max=0;
>     sum=0;
>     for(i=0;i<t;i++)
>     {
>         if(s[i].x==n)
>         {
>             temp=search(s[i].y);
>             if(temp>max) max=temp;
>             sum+=temp;
>         }
>         if(s[i].x>n) break;
>     }
>     flag[n]=max;
>     num[n]=sum;
>     return sum+1;
> }
>
> int cmp( const void *a , const void *b)
> {
> struct In *c = (In *)a;
> struct In *d = (In *)b;
> if(c->x != d->x) return c->x - d->x;
> else return c->y - d->y;
> }
>
> int main()
> {
>     int i,j,pp,min;
>
>     while(scanf("%d",&t)!=EOF)
>     {
>         s[0].x=0;
>         s[0].y=1;
>         for(i=1;i<t;i++)
>         scanf("%d%d",&s[i].x,&s[i].y);
>         qsort(s,t,sizeof(s[0]),cmp);
>         memset(flag,0,sizeof(flag));
>         search(0);
>
>         for(i=1;i<=t;i++)
>         if(flag[i]<(t-1-num[i])) flag[i]=(t-1-num[i]);
>
>         min=flag[1];
>         for(i=2;i<=t;i++)
>         {
>             if(min>flag[i]) min=flag[i];
>         }
>
>         pp=0;
>         for(i=1;i<=t;i++)
>         {
>             if(min==flag[i])
>             {
>                 if(pp==0)
>                 {
>                     printf("%d",i);
>                     pp=1;
>                 }
>                 else printf(" %d",i);
>             }
>         }
>         printf("\n");
>     }
>     return 0;
> }
>

```

Followed by: