P3243 [HNOI2015] 菜肴制作 の 题解

发布时间 2023-12-21 10:55:53作者: NFGase

本题是我的第一道蓝题,故我认为这道题稍难。

在本题解中,会列出一些坑点供大家参考。

这道题由优先制作这一关键词可知是一道拓扑排序的题,于是我想用邻接矩阵,但是我交之后错了,那是因为普通的数组会爆,但我不喜欢写链式前向星,故使用了vector的二维数组。

但是这道题比较特殊,由教练提醒,这道题需要跑反图,这是比较坑的一点。

还有,要注意需要得到一个队列的最大值,那么普通的标准库实现的队列是不行的,因为不能直接访问任意元素,再就是自己实现的,但是遍历有点慢,其他的数据结构又太复杂,所以我们只能使用优先队列,又称之为堆。

代码可能过长,就放在云剪贴板内。

记录