4010: [HNOI2015]菜肴制作
4010: [HNOI2015]菜肴制作
4010: [HNOI2015]菜肴制作
Time Limit: 5 Sec Memory Limit: 512 MB
Submit: 446 Solved: 251
Description
知名美食家小 A被邀请至ATM 大酒店，为其品评菜肴。
ATM 酒店为小 A 准备了 N 道菜肴，酒店按照为菜肴预估的质量从高到低给予
1到N的顺序编号，预估质量最高的菜肴编号为1。由于菜肴之间口味搭配的问题，
某些菜肴必须在另一些菜肴之前制作，具体的，一共有 M 条形如“i 号菜肴‘必须’
先于 j 号菜肴制作”的限制，我们将这样的限制简写为<i,j>。现在，酒店希望能求
出一个最优的菜肴的制作顺序，使得小 A能尽量先吃到质量高的菜肴：也就是说，
(1)在满足所有限制的前提下，1 号菜肴“尽量”优先制作；(2)在满足所有限制，1
号菜肴“尽量”优先制作的前提下，2号菜肴“尽量”优先制作；(3)在满足所有限
制，1号和2号菜肴“尽量”优先的前提下，3号菜肴“尽量”优先制作；(4)在满
足所有限制，1 号和 2 号和 3 号菜肴“尽量”优先的前提下，4 号菜肴“尽量”优
先制作；(5)以此类推。
例1：共4 道菜肴，两条限制<3,1>、<4,1>，那么制作顺序是 3,4,1,2。例2：共
5道菜肴，两条限制<5,2>、 <4,3>，那么制作顺序是 1,5,2,4,3。例1里，首先考虑 1，
因为有限制<3,1>和<4,1>，所以只有制作完 3 和 4 后才能制作 1，而根据(3)，3 号
又应“尽量”比 4 号优先，所以当前可确定前三道菜的制作顺序是 3,4,1；接下来
考虑2，确定最终的制作顺序是 3,4,1,2。例 2里，首先制作 1是不违背限制的；接
下来考虑 2 时有<5,2>的限制，所以接下来先制作 5 再制作 2；接下来考虑 3 时有
<4,3>的限制，所以接下来先制作 4再制作 3，从而最终的顺序是 1,5,2,4,3。
现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!” （不含引号，
首字母大写，其余字母小写）
Input
第一行是一个正整数D，表示数据组数。
接下来是D组数据。
对于每组数据：
第一行两个用空格分开的正整数N和M，分别表示菜肴数目和制作顺序限
制的条目数。
接下来M行，每行两个正整数x,y，表示“x号菜肴必须先于y号菜肴制作”
的限制。（注意：M条限制中可能存在完全相同的限制）
Output
输出文件仅包含 D 行，每行 N 个整数，表示最优的菜肴制作顺序，或
者”Impossible!”表示无解（不含引号）。
Sample Input
3 5 4 5 4 5 3 4 2 3 2 3 3 1 2 2 3 3 1 5 2 5 2 4 3
Sample Output
1 5 3 4 2 Impossible! 1 5 2 4 3
HINT
【样例解释】
第二组数据同时要求菜肴1先于菜肴2制作，菜肴2先于菜肴3制作，菜肴3先于
菜肴1制作，而这是无论如何也不可能满足的，从而导致无解。
100%的数据满足N,M<=100000,D<=3。
Source
题解：乍一看，做菜必须遵循一定的顺序，那么基本可以断定和TopSort有关，然后再看题目，貌似还要小号尽可能靠前（HansBug：特别提醒注意——是小号尽可能靠前，不是字典序最小，两者有很大区别），所以一开始我的反应就是求字典序最小的的拓扑序列，然后做出来一运行就粗线了前面所说的情况= =
然而，这个问题也不难解决，既然正着没办法，还不如反着来——1.反向建图 2.反向字典序最大，然后啪啪啪求了出来，然后倒着输出，就没了
PS：1.本蒟蒻由于太弱了，一时没想起来普通的堆怎么写（HansBug：只会写左偏树有木有TT），于是逗比的种了一棵线段树，功能是单点修改+查询最大位置的0（HansBug：好吧我比较逗请无视QAQ）
2.特别注意，这题数据貌似在每一行非Impossible!的输出最后貌似要保留一个空格，我一开始没保留结果PE了
1 /**************************************************************
2 Problem: 4010
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:2904 ms
7 Memory:11180 kb
8 ****************************************************************/
9
10 type
11 point=^node;
12 node=record
13 g:longint;
14 next:point;
15 end;
16 var
17 a:array[0..200000] of point;
18 e,b,c,f:array[0..100005] of longint;
19 d:array[0..1000005] of longint;
20 i,j,k,l,m,n:longint;
21 function max(x,y:longint):longint;
22 begin
23 if x>y then max:=x else max:=y;
24 end;
25 function min(x,y:longint):longint;
26 begin
27 if x<y then min:=x else min:=y;
28 end;
29 procedure swap(var x,y:longint);
30 var z:longint;
31 begin
32 z:=x;x:=y;y:=z;
33 end;
34 procedure add(x,y:longint);
35 var p:point;
36 begin
37 new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
38 end;
39 procedure built(z,x,y:longint);
40 begin
41 if x=y then
42 begin
43 d[z]:=e[x];
44 b[x]:=z;
45 end
46 else
47 begin
48 built(z*2,x,(x+y) div 2);
49 built(z*2+1,(x+y) div 2+1,y);
50 d[z]:=min(d[z*2],d[z*2+1]);
51 end;
52 end;
53 function getzero(z,x,y:longint):longint;
54 begin
55 if d[z]<>0 then exit(-1);
56 if (x=y) and (d[z]=0) then exit(x);
57 if d[z*2+1]=0 then exit(getzero(z*2+1,(x+y) div 2+1,y))
58 else exit(getzero(z*2,x,(x+y) div 2));
59 end;
60 procedure beep(x,y:longint);
61 begin
62 x:=b[x];
63 if y=maxlongint then d[x]:=maxlongint else inc(d[x],y);
64 while x>1 do
65 begin
66 x:=x div 2;
67 d[x]:=min(d[x*2],d[x*2+1]);
68 end;
69 end;
70 procedure pd;
71 var i,j,k,l,n,m:longint;p:point;
72 begin
73 readln(n,m);
74 fillchar(e,sizeof(e),0);
75 fillchar(f,sizeof(f),0);
76 fillchar(c,sizeof(c),0);
77 for i:=0 to n do a[i]:=nil;
78 for i:=1 to m do
79 begin
80 readln(j,k);
81 add(k,j);inc(e[j]);
82 end;
83 built(1,1,n);
84 for i:=1 to n do
85 begin
86 f[i]:=getzero(1,1,n);
87 if f[i]=-1 then
88 begin
89 writeln('Impossible!');
90 exit;
91 end;
92 c[f[i]]:=1;beep(f[i],maxlongint);
93 p:=a[f[i]];
94 while p<>nil do
95 begin
96 if c[p^.g]=0 then beep(p^.g,-1);
97 p:=p^.next;
98 end;
99 end;
100 for i:=n downto 1 do write(f[i],' ');
101 writeln;
102 i:=0;
103 end;
104 begin
105 readln(n);
106 for i:=1 to n do pd;
107 readln;
108
109 end.