HDU 2647 Reward(拓扑排序）

2 1
1 2
2 2
1 2
2 1

1777
-1

拓扑排序。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
typedef long long LL;
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int maxn=10100;
int head[maxn*2],next[maxn*2],end[maxn*2];
int in[maxn],val[maxn];
int n,m,cnt,k;
void toposort()
{
   int sum=0;
   k=0;
   queue<int>q;
   REPF(i,1,n)
     if(!in[i])  q.push(i);
   while(!q.empty())
   {
       int v=q.front();
       sum+=val[v];
       q.pop();
       k++;
       for(int i=head[v];i!=-1;i=next[i])
       {
           if(--in[end[i]]==0)
           {
             q.push(end[i]);
             val[end[i]]=val[v]+1;
           }
       }
   }
   if(k==n)  printf("%d\n",sum);
   else   printf("-1\n");
}
void add(int x,int y)
{
    next[cnt]=head[x];
    end[cnt]=y;
    head[x]=cnt++;
}
int main()
{
     int x,y;
     while(~scanf("%d%d",&n,&m))
     {
         cnt=0;
         REPF(i,1,n)   val[i]=888;
         CLEAR(in,0);
         CLEAR(head,-1);
         REP(i,m)
         {
             scanf("%d%d",&x,&y);
             add(y,x);
             in[x]++;
         }
         toposort();
     }
     return 0;
}

HDU 2647 Reward(拓扑排序）

原文：http://blog.csdn.net/u013582254/article/details/41734849