摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

當初以為真的是模擬題`XD 結果是模擬試題...

好啦,終於把題意釐清了...

作法:DFS

總之,看測資大小發現...一個點不連高過50個點.用相鄰矩陣做一個單向的連結

對每個點做一次 DFS 並比較,誰必須比誰高.(從每個點出發,計算的會不一樣所以比較MAX),但是如果不是一棵樹,就是會在 DFS 中 走回已經走過的點,若有這筆測資就是Poor Xed

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
int map[150000][50];
int top[150000]={0};
int start[150000]={0},appear[150000]={0};
int tt[500000]={0},sum=0,no=0;
void DFS (int now,int time)
{
  int a;
  if(no==1) return;
  if(tt[now]<time) tt[now]=time;
  for(a=0;a<top[now];a++)
    if(appear[map[now][a]]==0)
     {
           appear[map[now][a]]=1;
           DFS(map[now][a],time+1);
           appear[map[now][a]]=0;
     }
    else no=1;
}
main()
{
 int n,m;
 while(scanf("%d %d",&n,&m)==2)
   {
     int a,b,t1,t2;
     for(a=0;a<m;a++)
      {
        scanf("%d %d",&t2,&t1);
        map[t1][top[t1]]=t2;
        top[t1]++;
        start[t2]++;
      }
     for(a=1;a<=n;a++)
         {
           appear[a]=1;
           DFS(a,0);
           appear[a]=0;
         }
     for(a=0;a<=n;a++) sum=sum+tt[a];
      if(no==0)
       printf("%d\n",n*100+sum);
      else printf("Poor Xed\n");
   }
 return 0;
}