题目链接：

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

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

代码：

1 #include
     
        2 #include
      
        3 #include
       
         4 #include
        
          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
         
          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\n",toposort());69     }70     return 0;71 }