雪竹的天空

theorix

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  34 随笔 :: 0 文章 :: 20 评论 :: 0 Trackbacks
 1 #include<iostream>
 2 using namespace std;
 3 int in[209];
 4 int map[209][209];
 5 int ans[209];
 6 int main()
 7 {
 8     int ca;
 9     scanf("%d",&ca);
10     while(ca--)
11     {
12         int n,m;
13         scanf("%d%d",&n,&m);
14         int i,j,k;
15         int a,b;
16         memset(map,0,sizeof(map));
17         memset(in,0,sizeof(in));
18         for(i=1;i<=m;i++)
19         {
20             scanf("%d%d",&a,&b);
21             if(map[a][b]==0)
22             {
23                 map[a][b]=1;
24                 in[a]++;
25             }
26         }
27         memset(ans,0,sizeof(ans));
28         int cnt=n;
29         while(true)
30         {
31             for(i=n;i>=1;i--)
32                 if(ans[i]==0&&in[i]==0)
33                     break;
34             if(i==0)
35                 break;
36             ans[i]=cnt--;
37             for(j=1;j<=n;j++)
38                 if(map[j][i]==1)
39                     in[j]--;
40         }
41         if(cnt==0)
42         {
43             for(i=1;i<=n;i++)
44             {
45                 if(i>1)printf(" ");
46                 printf("%d",ans[i]);
47             }
48             printf("\n");
49         }
50         else
51             printf("-1\n");
52     }
53 }
54 
55 
posted on 2008-09-04 23:12 雪竹的天空( theorix ) 阅读(1103) 评论(3)  编辑 收藏 引用

评论

# re: pku 3687 Labeling Balls ( 有点难想的贪心算法 ) 2008-09-04 23:15 <font color="red">雪竹的天空( theorix )
之前想了两种贪心都不对 原来是要倒着贪心  回复  更多评论
  

# re: pku 3687 Labeling Balls ( 有点难想的贪心算法 ) 2009-05-13 19:21 sdfsf
不错,很简洁!!  回复  更多评论
  

# re: pku 3687 Labeling Balls ( 有点难想的贪心算法 )[未登录] 2009-09-01 09:10 111
牛!  回复  更多评论
  


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