hdu2647Reward（拓扑排序）

http://acm.hdu.edu.cn/showproblem.php?pid=2647

定义一个数组来标记保证每次循环找到的是同一层次的它们加的数是相同的用f来表示找到多少个入度为0的点 <n时有环输出-1

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 struct node
 4 {
 5     int v,w,next;
 6 }men[20001];
 7 int first[10001],de[10001],t,kk[10001];
 8 void init()
 9 {
10     t = 0;
11     memset(first,-1,sizeof(first));
12 }
13 void add(int u,int v)
14 {
15     men[t].v = v;
16     men[t].next = first[u];
17     first[u] = t;
18     t++;
19 }
20 void topo(int n)
21 {
22     int i,j,k,f = 0,o=0;
23     __int64 s = 0,w=888,g;
24     memset(kk,0,sizeof(kk));
25     for(i = 1; i <= n ; i++)
26     {
27         for(j = 1 ; j <= n ;j++)
28         {
29             if(kk[j]==i-1&&de[j]==0)
30             {
31                 de[j] = -1;
32                 f++;                
33                 g = w+i-1;//根据层次 来加增量
34                 s+=g;                
35                 for(k = first[j] ; k!=-1 ; k = men[k].next)
36                 {
37                     de[men[k].v]--;
38                     if(de[men[k].v]==0)
39                         kk[men[k].v] = i;//层次不一样 下次再循环
40                 }
41             }        
42         }
43     }
44     if(f<n)
45         printf("-1\n");
46     else
47         printf("%I64d\n",s);
48 }
49 int main()
50 {
51     int i,j,k,n,m,a,b;
52     while(scanf("%d%d", &n,&m)!=EOF)
53     {
54         memset(de,0,sizeof(de));
55         init();
56         for(i = 1; i <= m ; i++)
57         {
58             scanf("%d%d", &a,&b);
59             add(b,a);
60             de[a]++;
61         }
62         topo(n);
63     }
64     return 0;
65 }