4010: [HNOI2015]菜肴制作

4010: [HNOI2015]菜肴制作

Time Limit: 5 Sec  Memory Limit: 512 MB

Submit: 446  Solved: 251

[Submit][Status][Discuss]

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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(九)附两道扩展题答案

前言 在上文程序员进阶之算法练习(八)附两道搜狐笔试题中,在搜狐笔试题的基础上稍微改编后的题目: 《宝石二》 有一串宝石首尾相连,用一个大写字母表示一个宝...

41970
来自专栏数据结构与算法

Day2上午解题报告

预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

46940
来自专栏数据结构与算法

12:加密的病历单

12:加密的病历单 总时间限制: 1000ms 内存限制: 65536kB描述 小英是药学专业大三的学生,暑假期间获得了去医院药房实习的机会。  在药房实习期...

39140
来自专栏喔家ArchiSelf

IOT语义互操作性之本体论

这个系列文章描述了一个单一的语义数据模型来支持物联网和建筑、企业和消费者的数据转换。 这种模型必须简单可扩展, 以便能够在各行业领域之间实现插件化和互操作性。 ...

13850
来自专栏owent

09年8月9日 ECUST ACM 练习赛总结

B题补充: B题的DP方法比较诡异(起码我理解了很久) 令fn[i][j]为有i个数j次交换位置的排列数量 很明显,当i+1时,如果把新增的数放在最后一位...

7620
来自专栏NetCore

关于某道C#上机题的OO

前两天在园子里,有人出了一道《关于一道C#上机题的一点想法》,大概的意思呢是利用OO的思想来进行编程,接着又有一位朋友,也写了自己的答案,此朋友非常厉害,从类图...

23560
来自专栏专知

关关的刷题日记78 – Leetcode 69. Sqrt(x)

关关的刷题日记78 – Leetcode 69. Sqrt(x) 题目 Implement int sqrt(int x). Compute and retur...

36460
来自专栏阮一峰的网络日志

为什么Lisp语言如此先进?(译文)

上周,《黑客与画家》总算翻译完成,已经交给出版社了。 翻译完这本书,累得像生了一场大病。把书稿交出去的时候,心里空荡荡的,也不知道自己得到了什么,失去了什么。 ...

32260
来自专栏HansBug's Lab

2748: [HAOI2012]音量调节

2748: [HAOI2012]音量调节 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 719  Solve...

30680
来自专栏HansBug's Lab

1935: [Shoi2007]Tree 园丁的烦恼

1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

31580

扫码关注云+社区

领取腾讯云代金券