BZOJ 3875 [Ahoi2014] 骑士游戏

发布于 2017-08-18  174 次阅读


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

https://loj.ac/problem/2225

题意:见 loj 题面。


做不上原题的我真是太弱了 T.T

如果考虑 dp 的话,式子是很好写出的:\(dp_i=min(k_i,\sum dp_{son[i]})\)

如果原图是个 dag 可以按照拓扑序搞,然而不是...

之前做 fks 大爷模拟赛的时候学到了用 spfa 迭代同层后效性 dp,然而一做题就忘了...

对于某些 dp 是具有同层后效性的,也就是说同层的 dp 值可以相互转移(尽管此题只有一层)

我们可以对应转移关系建立图论模型,跑 spfa 来多次迭代,每次松弛就将这个点能更新到的点都入队,就跑的飞起了...

 


一个非常弱的准退役OIER