bzoj4010专题

BZOJ4010: [HNOI2015]菜肴制作(优先队列拓扑排序)

Description 知名美食家小 A被邀请至ATM 大酒店,为其品评菜肴。 ATM 酒店为小 A 准备了 N 道菜肴,酒店按照为菜肴预估的质量从高到低给予 1到N的顺序编号,预估质量最高的菜肴编号为1。由于菜肴之间口味搭配的问题, 某些菜肴必须在另一些菜肴之前制作,具体的,一共有 M 条形如“i 号菜肴‘必须’ 先于 j 号菜肴制作”的限制,我们将这样的限制简写为<i,j>。现在,酒店希望能

bzoj4010: [HNOI2015]菜肴制作

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4010 思路:显然最小字典序是错误的,那么应该怎么求? 直接选小的在前不一定对,但是如果没有都没有后继,大的在后面一定是对的 所以考虑倒着DP,求出最大拓扑序,反向输出即可 #include<queue>#include<cstdio>#include<cstrin