cdoj916-方老师的分身 III 【拓扑排序】

http://acm.uestc.edu.cn/#/problem/show/916

方老师的分身 III

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

一天的讲座结束后，方老师的分身们聚在了一起。在合并成一个方老师之前。这些分身要求方老师的真身发糖。这些分身要求方老师至少给他们发888个糖。这还不够，有的分身要求分比另外某个分身的糖多。问方老师最少分多少糖。

Input

有多组数据。

第一行2个整数N（1≤N≤10000），M（0≤M≤20000）表示分身数和要求数。

接下来m行，每行2个整数x，y。表示x要求分的比y更多糖果。

Output

一个整数，方老师最少要分多少糖。如过无法完成分糖输出−1。

Sample input and output

2 1 1 2 2 2 1 2 2 1

1777 -1

题解：很容易想到拓扑排序。题目里设计环，用拓扑排序可以判断环的存在。另外需要注意，拓扑的方向。

代码：

 #include <fstream>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int cnt=;

 const int N=;

 const int M=;

 int n,m;

 int u[M],v[M],head[N],la[M];

 int du[N],cn[N];

 bool b;

 void topology();

 int main()

 {

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     while(~scanf("%d%d",&n,&m)){

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

         memset(du,,sizeof(du));

         memset(cn,,sizeof(cn));

         for(int i=;i<m;i++){

             scanf("%d%d",&v[i],&u[i]);

             la[i]=head[u[i]];

             head[u[i]]=i;

             du[v[i]]++;

         }

         b=true;

         topology();

         if(b){

             int ans=cnt*n;

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

                 ans+=cn[i];

             }

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

         }else{

             puts("-1");

         }

     }

     return ;

 }

 void topology(){

     int top=-;

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

         if(!du[i])  du[i]=top,top=i;

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

         if(top==-){

             b=false;

             return;

         }else{

             int j=top;

             top=du[top];

             for(int k=head[j];k!=-;k=la[k]){

                 cn[v[k]]=max(cn[v[k]],cn[j]+);

                 if(!(--du[v[k]]))   du[v[k]]=top,top=v[k];

             }

         }

     }

 }