方老师的分身 III

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

一天的讲座结束后，方老师的分身们聚在了一起。在合并成一个方老师之前。这些分身要求方老师的真身发糖。这些分身要求方老师至少给他们发

Input

有多组数据。

第一行

接下来

Output

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

Sample input and output

Sample Input	Sample Output
2 1 1 2 2 2 1 2 2 1	1777 -1

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

代码：

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int cnt=888;
 9 const int N=10005;
10 const int M=20005;
11 int n,m;
12 int u[M],v[M],head[N],la[M];
13 int du[N],cn[N];
14 bool b;
15 
16 void topology();
17 
18 int main()
19 {
20     //freopen("D:\input.in","r",stdin);
21     //freopen("D:\output.out","w",stdout);
22     while(~scanf("%d%d",&n,&m)){
23         memset(head,-1,sizeof(head));
24         memset(du,0,sizeof(du));
25         memset(cn,0,sizeof(cn));
26         for(int i=0;i<m;i++){
27             scanf("%d%d",&v[i],&u[i]);
28             la[i]=head[u[i]];
29             head[u[i]]=i;
30             du[v[i]]++;
31         }
32         b=true;
33         topology();
34         if(b){
35             int ans=cnt*n;
36             for(int i=1;i<=n;i++){
37                 ans+=cn[i];
38             }
39             printf("%d
",ans);
40         }else{
41             puts("-1");
42         }
43     }
44     return 0;
45 }
46 void topology(){
47     int top=-1;
48     for(int i=1;i<=n;i++)
49         if(!du[i])  du[i]=top,top=i;
50     for(int i=0;i<n;i++){
51         if(top==-1){
52             b=false;
53             return;
54         }else{
55             int j=top;
56             top=du[top];
57             for(int k=head[j];k!=-1;k=la[k]){
58                 cn[v[k]]=max(cn[v[k]],cn[j]+1);
59                 if(!(--du[v[k]]))   du[v[k]]=top,top=v[k];
60             }
61         }
62     }
63 }