http://acm.hdu.edu.cn/showproblem.php?pid=2647
1 #include<stdio.h>
2 #include<stdlib.h>
3 #define M 10001
4 struct H{
5 int num;
6 struct H * next;
7 }hh[M],*tail[M];
8 int hash[M];
9 int q[M];
10 int main()
11 {
12 int n,m,a,b,i,sum,count,f,l,num;
13 struct H *p;
14 while (scanf("%d%d",&n,&m)==2)
15 {
16 memset(hash,0,sizeof(hash));
17 num = 0;
18 while (m--)
19 {
20 scanf("%d%d",&a,&b);
21 if(hash[a]==0)
22 {
23 num ++;
24 hash[a] = 1;
25 hh[a].num = 0;
26 hh[a].next =NULL;
27 tail[a] = &hh[a];
28 }
29 if(hash[b]==0)
30 {
31 num ++;
32 hash[b] = 1;
33 hh[b].num = 0;
34 hh[b].next =NULL;
35 tail[b] = &hh[b];
36 }
37 hh[a].num ++;
38 p = (struct H * )malloc(8);
39 p->next = NULL;
40 p->num = a;
41 tail[b]->next = p;
42 tail[b] = tail[b]->next;
43 }
44 sum = count = 0;
45 l = 0;
46 for(i=1;i<M;i++)
47 if(hash[i] && hh[i].num == 0)
48 {
49 count ++;
50 q[l++] = i;
51 hh[i].num = 0;
52 }
53 f = 0;
54 while (f<l)
55 {
56 p = hh[q[f]].next;
57 while (p!=NULL)
58 {
59 a = p->num;
60 hh[a].num --;
61 if (hh[a].num == 0)
62 {
63 count ++;
64 hh[a].num = hh[q[f]].num +1;
65 sum += hh[a].num;
66 q[l++] = a;
67 }
68 p = p->next;
69 }
70 f++;
71 }
72 if(count!=num)
73 puts("-1");
74 else
75 printf("%d\n",888*n + sum);
76 }
77 }
posted on 2009-02-09 22:39
shǎ崽 閱讀(764)
評論(0) 編輯 收藏 引用