HDU 2647 Reward（トポロジーソート）

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2647
タイトル:
Reward
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：6207    Acceepted Submission(s)：1918
Problem Description
Dandelion's uncle is a boss of a factory.As the spring festival is cording，he wants to distribute rewards to his works.Now he has a trout how to distribute the rewards.
The work s Will cocorererewards、and some one may have demands of the diststributing of rewards、just like a's reward shororororormothan b's.Dandelion's unclue wants to fulfill all thedemandndnds s、of corererererererererererererererererelfill thededededemands s s s s s s s s s s s s s s thedededededededededededededededededededededemandlelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelele
 
Input
One line with two integers n and m，stands for the number of works and the number of demands.（n<=10000,m==20000）
then m line s、each line contains two integers a and b、stands fora's reward shoruld be more than b's.
 
Output
For evercase，print the least money dandelion's uncle needs to distribute.If it's impossible to fulfill all the works'demands，print-1.
 
Sample Input

   
   
   
   

    
    
    
    2 1
1 2
2 2
1 2
2 1
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1777
-1
   
   
   
   

 
Author
dandelion
 
タイトルの大意:
     社長はボーナスを出します。一人当たり少なくとも888元です。いくつかの要求があります。aの給料はbの給料より高いです。もし矛盾した関係があるならば、-1を出力して、さもなくば出力はできるだけいくらを必要とします。
問題を解く:
    比較的に明らかなトポロジ順序付けは、他のテーマとは違って、ノードが多く、隣接テーブルを必要とする。同時にすべての人に権利を分ける必要があります。一つの点は多くの点がそれより小さいかもしれません。この時はすべての権利の中の最大値を取る必要があります。それがすべてのそれより小さい値より大きいことを保証します。
コード:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
using namespace std;
//s     ，     
set <int> s;
//     ，  ，       ，cnt        
int val[10010],in[10010],head[10010],cnt=0;
//     
bool vis[10010];
//    
struct edge
{
	int to,next;
}ee[20010];
//     
void add_edge(int a,int b)
{
	ee[cnt].to=b;
	//       
	ee[cnt].next=head[a];
	head[a]=cnt++;
}
queue <int> qe;
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	
	int n,m,a,b,tmp,ans,cur,v,to;
	bool flag;
	while(~scanf("%d%d",&n,&m))
	{
	   flag=true;
       cnt=0;
       ans=0;
       while(!qe.empty())
         qe.pop();
	   s.clear();
	   //    
	   for(int i=1;i<=n;i++)
	     val[i]=888;
       //    
       memset(in,0,sizeof(in));
       memset(head,-1,sizeof(head));
       memset(vis,0,sizeof(vis));
	   for(int i=0;i<m;i++)
	   {
 	     //    ，wa    
   		 scanf("%d%d",&b,&a);
   		 tmp=a*10000+b;
   		 //   
   		 if(!s.count(tmp))
   		 {
   		 	//  ，    ，    ，   0 
 		   	add_edge(a,b);
 		   	in[b]++;
	     }
   	   }
	   for(int i=1;i<=n;i++)
	   {
   		  if(in[i]==0)
   		  {
  		     qe.push(i);
			 ans+=888;
			 vis[i]=1; 	
	      }
   	   }
	   while(!qe.empty())
	   {
   		  cur=qe.front();
   		  qe.pop();
   		  v=val[cur]+1;
   		  for(int i=head[cur];i!=-1;i=ee[i].next)
   		  {
 	         to=ee[i].to;
 	         //    ，      
  		     val[to]=max(val[to],v);
  		     //       0   
			 in[to]--;
			 if(in[to]==0)
			 {
 			    ans+=val[to];
				vis[to]=1;
				qe.push(to);	
		     } 	
	      }
   	   }
   	   //          ，       
	   for(int i=1;i<=n;i++)
	   {
   		  if(!vis[i])
   		  {
  		   	flag=false;
  		   	break;
	      }
   	   }
	   if(flag)
	     printf("%d
",ans);
	   else
	     printf("-1
");	
	}
	return 0;
}