[BZOJ3875][AHOI2014]骑士游戏(松弛操作)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=3875

分析:

类似于spfa求最短路,设d[i]表示完全消灭i号怪物的最小花费,我们对d[]进行动态更新

我们可以把问题反向:一开始所有怪物都存活,我们要找到一个怪物合成方案合成1号怪物,其中合成方法有两种,一种是魔法攻击逆向产生怪物,另一种就是由某个怪物的后继怪物合成此怪物

对于第一种产生方法的表示,令初始的d[i]=k[i]即可

对于第二种产生方法的表示,也就是算法的核心——类似于spfa的“松弛”

但这里松弛操作的条件不太一样,这里松弛操作的条件是d[i]>s[i]+∑d[j] (j是i的后继)

于是算法就出来了:

1、将1~n号怪物加入队列,初始d[i]=k[i](表示用魔法攻击逆向产生)

2、依次访问队列中的每个节点i,如果d[i]>s[i]+∑d[j]则进行松弛操作更新d[i],并且把节点i的所有前继(注意不是后继)加入队列进行下一轮的更新(如果前继已经在队列中存在就不加入)

3、ans=d[1]

上一篇:Confluence 6 指定日志选项和已知问题


下一篇:模拟jQuery中的ready方法及实现按需加载css,js实例代码