随笔-72  评论-126  文章-0  trackbacks-0

 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*+ sum);
76     }
77 }
posted on 2009-02-09 22:39 shǎ崽 阅读(749) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理