dango

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

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

[POJ 1636] Prison rearrangement

原题地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1636

题目大意:

拥有同样容量m的两个监狱打算交换一些犯人(<=m/2),但是有一些囚犯不可以放在同一个监狱里头。问最多可以交换多少人(再多也不能超过m/2)

题目分析:

不妨把监狱称为A和B。当存在牵连关系时,A中的某个犯人移动到B,会牵动B中一些犯人移动到A,如此反复……其实也就是如果要移动A,其最终结果是A中的一部分人和B中的一部分人整体交换。那么就需要求出这样的一个交换关系(传递闭包)。

思路:

用一个暴力的Floyd来解决传递闭包的问题,再用一个经典的二维背包来解决移动问题。其实算法都是很基础的,但是还是TLE了两次,原因在于对一些细节的不注意。

有些时候看似危险的复杂度,其实只要把一些细节考虑好了,就可以从TLE跨越到AC。尤其是常见的floyd,加了一行小小的连优化都不算的判断就从TLE变为AC了。

下面代码里头把原来TLE的部分也留在注释里,自己引以为戒。

代码:

 

POJ 1636
posted on 2010-08-26 20:39 Dango 阅读(414) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理