AC. 梦想

frank_c1

[HNOI 2015] 菜肴制作

发布于2016年06月02日 | 暂无评论 | 466阅读 | 贪心

题目描述

知名美食家小A被邀请至ATM大酒店,为其品评菜肴。

ATM酒店为小A准备了n道菜肴,酒店按照为菜肴预估的质量从高到低给予1n的顺序编号,预估质量最高的菜肴编号为1。由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有m条形如“i号菜肴必须先于j号菜肴制作”的限制,我们将这样的限制简写为(i,j)。现在,酒店希望能求出一个最优的菜肴的制作顺序,使得小A能尽量先吃到质量高的菜肴。也就是说

1.在满足所有限制的前提下,1号菜肴“尽量”优先制作;

2.在满足所有限制,1号菜肴“尽量”优先制作的前提下,2号菜肴“尽量”优先制作;

3.在满足所有限制,1号和2号菜肴“尽量”优先的前提下,3号菜肴“尽量”优先制作;

4.在满足所有限制,1号和2号和3号菜肴“尽量”优先的前提下,4号菜肴“尽量”优先制作;

5.以此类推。

现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!” (不含引号,首字母大写,其余字母小写)

输入格式

第一行是一个正整数D,表示数据组数。

接下来是D组数据。对于每组数据:

第一行两个用空格分开的正整数nm,分别表示菜肴数目和制作顺序限制的条目数。

接下来m行,每行两个正整数x,y,表示“x号菜肴必须先于y号菜肴制作”的限制。

注意:m条限制中可能存在完全相同的限制。

1 \le n,m \le 100000,D \le 3

输出格式

输出文件仅包含D行,每行n个整数,表示最优的菜肴制作顺序,或者”Impossible!”表示无解(不含引号)。

题目解析

这样的题怎么就轻易地HNOI了呢……(但其实还是有坑点的~)

拓扑排序,但不是字典序最小。

注意到我们可以将图中所有边反向,每次取出入度为0的编号最大的点。这样我们就可以保证编号小的尽量在后面。

最后倒序输出就好啦。时间复杂度O(n \log n)