拓扑排序——奖金

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int maxn=9999;
 6 int n,m,u,v,money;
 7 int a[maxn][maxn],du[maxn];
 8 int zh[maxn];
 9 
10 bool topsort()
11 {
12     int tot=0,k=0,hh;
13     while(tot<n)
14     {
15         hh=0;
16         for(int i=1;i<=n;i++)
17         {
18             if(!du[i])
19             {
20                 du[i]=0x7fffffff;
21                 tot++;
22                 hh++;
23                 zh[hh]=i;
24                 money+=100;
25             }
26         }
27             money+=k*hh;
28             k++;
29             if(hh==0) return 0;
30             for(int i=1;i<=hh;i++)
31               for(int j=1;j<=a[zh[i]][0];j++)
32                 du[a[zh[i]][j]]--; 
33     }
34     return 1;
35 }
36 
37 int main()
38 {
39     cin>>n>>m;
40     for(int i=1;i<=m;i++){
41         cin>>u>>v;
42         a[v][0]++;
43         a[v][a[v][0]]=u;
44         du[u]++;
45     }
46     if(topsort()) cout<<money<<endl;
47     else cout<<"Poor Xed"<<endl;
48     return 0;
49 }