细草微风岸

平凡而不平庸

常用链接

统计

最新评论

hdu 3339 0-1背包+最短路

     本题开始题意理解有问题,以为是坦克一起开到每个地方炸掉station,使总路程最短,于是要考虑各个station之间的路程,而近于搜索暴力,百思不得其解。后来发现题意理解错了。“We have enough tanks”这句话不是白写的,要仔细读题。是把各个坦克开到各个地方守着,就是control(控制)power总量在占据一半以上的station,使之不能启动,于是就可以背包了。
     首先求出各个station到开始位置的单源最短路,这里边数范围是点数范围的平方关系,用Dijkstra和spfa都可以,这是背包里面的价值。各个station总的power是背包容量,每个station的power是物品的容量。在容量一半以上的范围内找价值最小的。

     代码如下:

代码

posted on 2011-07-29 17:53 鲍青 阅读(193) 评论(0)  编辑 收藏 引用


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