雅禮中學2007模擬試題 獎金(reward)
當初以為真的是模擬題`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;
}