HDU 2647 Reward（拓扑排序+判断环+分层）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2647

题目大意：要给n个人发工资，告诉你m个关系，给出m行每行a b，表示b的工资小于a的工资，最低工资为888，求最少要发多少工资，如果关系矛盾就输出“-1”。

解题思路：用拓扑排序解决，但是要分层，类似于多棵树的层次遍历，用dis[i]存储i所在层数（起点为0层），因为要是所有条件都符合，所以dis[i]取最大值。还有注意判断是否存在环。

代码：

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 using namespace std;
 6 const int N=1e4+5;
 7 
 8 struct node{
 9     int to,next;
10 }edge[2*N];
11 
12 int n,m,idx;
13 int head[N],vis[N],degree[N],dis[N];
14 
15 void init(){
16     idx=1;
17     memset(head,0,sizeof(head));
18     memset(degree,0,sizeof(degree));
19     memset(dis,0,sizeof(dis));
20 }
21 
22 void addedge(int u,int v){
23     edge[idx].to=v;
24     edge[idx].next=head[u];
25     head[u]=idx++;
26 }
27 
28 int toposort(){
29     queue<int>q;
30     for(int i=1;i<=n;i++){
31          if(degree[i]==0)
32              q.push(i);
33     }
34     int cnt=0;
35     while(!q.empty()){
36         int k=q.front();
37         q.pop();
38         degree[k]--;
39         cnt++;
40         for(int j=head[k];j;j=edge[j].next){
41             node t=edge[j];
42             degree[t.to]--;
43             dis[t.to]=max(dis[t.to],dis[k]+1);
44             if(degree[t.to]==0)
45                 q.push(t.to);
46         }
47     }
48     int ans=0;
49     //判断环 
50     if(cnt!=n)
51          ans=-1;
52     else{
53         for(int i=1;i<=n;i++)
54             ans+=dis[i]+888;
55     }
56     return ans;
57 }
58 
59 int main(){
60     while(~scanf("%d%d",&n,&m)){
61         init();
62         for(int i=1;i<=m;i++){
63             int a,b;
64             scanf("%d%d",&a,&b);
65             addedge(b,a);
66             degree[a]++;
67         }
68         printf("%d
",toposort());
69     }
70     return 0;
71 }