3243

前言 今天考试考到这道题，挂惨了。 题意 有 \(n\) 道菜肴，编号为 \(1 \sim n\)。有 \(m\) 个条件，形如 \((i, j)\)，表示菜肴 \(i\) 必须在菜肴 \(j\) 之前制作。需求出一个菜肴的制作顺序，满足： 在满足所有限制的前提下，\(1\) 号菜肴尽量优先制作。 ......

本题是我的第一道蓝题，故我认为这道题稍难。 在本题解中，会列出一些坑点供大家参考。 这道题由优先制作这一关键词可知是一道拓扑排序的题，于是我想用邻接矩阵，但是我交之后错了，那是因为普通的数组会爆，但我不喜欢写链式前向星，故使用了vector的二维数组。 但是这道题比较特殊，由教练提醒，这道题需要跑反 ......

这道题难点就在如何贪心，这里要我们让最小的尽可能优先做而不是字典序最小，那我们让大的尽可能后做，是不是就可以把最小的尽可能优先做呢？而这样相当于是反过来的序列字典序最大，所以我们跑个反图最大字典序拓扑即可，即建反图以后用优先队列维护最大点。 \(Code\) const int N=1e5+5; i ......

## P3243 菜肴制作 题意给出由n个节点组成的有向（不一定无环）图，给出m组限制 **（i，j）** 代表i节点必须先于j被访问，现询问在满足所有限制的情况下，访问顺序字典序最小的一种 首先考虑 **Impossible** 的情况：当图出现环的时候产生矛盾，所以只要判定有没有环就好了 ### ......

# [P3243 [HNOI2015] 菜肴制作](https://www.luogu.com.cn/problem/P3243) ## 题目描述 知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。ATM 酒店为小 A 准备了 $n$ 道菜肴，酒店按照为菜肴预估的质量从高到低给予 $1$ 到 ......