hdu2647 Reward 拓扑排序

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

此题的关键在于分层次，最低一层的人的奖金是888，第二层是888+1 ……

分层可以这样实现。建立反向图。在拓扑排序的时候，第一批入度为0的点就处于第一层，第二批处于第二层 ……

由于是逐个遍历入度为0的点，所以怎么实现上面所说的第一批，第二批就需要动点脑。

可以试试下面的测试数据：

4 3
1 3
2 3
4 3

4 3
1 2
2 3
4 3

4 2
1 2
3 4

6 3
1 2
3 4
5 6

测试结果依次是：　　3555　　3556　　3554 　　5331

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = , M =;

 struct node

 {

     int to,  next;

 };

 node edge[M];

 int ind[N], head[N],que[N],ans[N];

 int iq,tot,t;

 void topo(int n)

 {

     int i,k,j=,x,y;

     t=-;x=;

     for(i=;i<=n;i++)

         if(ind[i]==) que[j++]=i;

     ans[++t]=j-x;

     y=;

     x=j;

     for(i=;i<j;i++)

     {

         if(i==ans[t]+y)

         {

             ans[++t]=j-x;

             x=j;

             y=i;

         }

         int u=que[i];

         for(k=head[u]; k!=-; k=edge[k].next)

         {

             ind[edge[k].to]--;

             if(ind[edge[k].to]==)

                 que[j++]=edge[k].to;

         }

     }

     iq=j;

 }

 void addedge(int i,int j)

 {

     edge[tot].to=j;edge[tot].next=head[i];head[i]=tot++;

 }

 void init()

 {

     tot=;

     memset(ind,,sizeof(ind));

     memset(head,-,sizeof(head));

 }

 int main()

 {

     //freopen("test.txt","r",stdin);

     int n,m,i,j,k;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         init();

         int flag=;

         while(m--)

         {

             scanf("%d%d",&i,&j);

             if(i==j) flag=;

             if(flag) continue;

             ind[i]++;

             addedge(j,i);

         }

         topo(n);

         if(iq<n||flag) printf("-1\n");

         else

         {

             int s=;

             for(i=;i<=t;i++) s+=ans[i]*(i+);

             printf("%d\n",s);

         }

     }

     return ;

 }