dango

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Hdu 3231 Box Relations

题目描述:

    原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=3231

    给定一些正方体的关系,要求一组符合这些关系的正方体坐标,如果不存在符合条件的正方体坐标,IMPOSSIBLE。(Special Judge)

 

题目分析:

    首先把正方体这个立体问题拆分成X,Y,Z三个维度上的的平面问题。三个维度上的平面问题处理完了,正方体问题也就处理完了。

    首先想到了差分约束系统,但是我的SPFA呃,TLE了……(求一个不TLE的差分约束系统标程……)

    上网搜索了一个大牛的文,说只需要拓补排序就可以了,完全不需要差分约束。

    再想一想,此题如果用差分约束系统来做,所有边权都是-1。其实不如更直观地进行构图,例如a<b,那么就构图map[a][b] = 1,也就是不妨看做a到b的边权为1。其实进行一下拓补排序,根据点的拓补排序的结果就可以直接作为答案输出,如果拓补排序失败也就是IMPOSSIBLE。

 

代码:

hdu3231
posted on 2010-08-26 20:44 Dango 阅读(728) 评论(0)  编辑 收藏 引用

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