题目描述
知名美食家小 A 被邀请至 ATM 大酒店,为其品评菜肴。
ATM 酒店为小 A 准备了 NNN 道菜肴,酒店按照为菜肴预估的质量从高到低给予 111 到 NNN 的顺序编号,预估质量最高的菜肴编号为 111。由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有 MMM 条形如「iii 号菜肴『必须』先于 jjj 号菜肴制作”的限制」,我们将这样的限制简写为 ⟨i,j⟩\langle i,j \rangle⟨i,j⟩。
现在,酒店希望能求出一个最优的菜肴的制作顺序,使得小 A 能尽量先吃到质量高的菜肴:也就是说,
- 在满足所有限制的前提下,111 号菜肴「尽量」优先制作;
- 在满足所有限制,111 号菜肴「尽量」优先制作的前提下,222 号菜肴「尽量」优先制作;
- 在满足所有限制,111 号和 222 号菜肴「尽量」优先的前提下,333 号菜肴「尽量」优先制作;
- 在满足所有限制,111 号和 222 号和 333 号菜肴「尽量」优先的前提下,4 号菜肴「尽量」优先制作;
- 以此类推。
例一:共四道菜肴,两条限制 ⟨3,1⟩\langle 3,1 \rangle⟨3,1⟩、⟨4,1⟩\langle 4,1 \rangle⟨4,1⟩,那么制作顺序是 3,4,1,23,4,1,23,4,1,2。
例二:共五道菜肴,两条限制 ⟨5,2⟩\langle 5,2 \rangle⟨5,2⟩、⟨4,3⟩\langle 4,3 \rangle⟨4,3⟩,那么制作顺序是 1,5,2,4,31,5,2,4,31,5,2,4,3。
例一里,首先考虑 111,因为有限制 ⟨3,1⟩\langle 3,1 \rangle⟨3,1⟩ 和 ⟨4,1⟩\langle 4,1 \rangle⟨4,1⟩,所以只有制作完 333 和 444 后才能制作 111,而根据(3),333 号又应「尽量」比 444 号优先,所以当前可确定前三道菜的制作顺序是 3,4,13,4,13,4,1;接下来考虑 222,确定最终的制作顺序是 3,4,1,23,4,1,23,4,1,2。
例二里,首先制作 111 是不违背限制的;接下来考虑 222 时有 ⟨5,2⟩\langle 5,2 \rangle⟨5,2⟩ 的限制,所以接下来先制作 555 再制作 222;接下来考虑 333 时有 ⟨4,3⟩\langle 4,3 \rangle⟨4,3⟩ 的限制,所以接下来先制作 444 再制作 333,从而最终的顺序是 1,5,2,4,31,5,2,4,31,5,2,4,3。
现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!
” (不含引号,首字母大写,其余字母小写)
输入格式
第一行是一个正整数 DDD,表示数据组数。
接下来是 DDD 组数据。
对于每组数据:
第一行两个用空格分开的正整数 NNN 和 MMM,分别表示菜肴数目和制作顺序限制的条目数。
接下来 MMM 行,每行两个正整数 x,yx,yx,y,表示「xxx 号菜肴必须先于 yyy 号菜肴制作」的限制。(注意:MMM 条限制中可能存在完全相同的限制)
输出格式
输出文件仅包含 DDD 行,每行 NNN 个整数,表示最优的菜肴制作顺序,或者”Impossible!
”表示无解(不含引号)。
样例
样例输入
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
样例输出
1 5 3 4 2
Impossible!
1 5 2 4 3
样例解释
第二组数据同时要求菜肴 111 先于菜肴 222 制作,菜肴 222 先于菜肴 333 制作,菜肴 333 先于菜肴 111 制作,而这是无论如何也不可能满足的,从而导致无解。
数据范围与提示
对于100%100 \%100% 的数据,N,M≤100000, D≤3N,M \leq 100000,\ D \leq 3N,M≤100000, D≤3。
这个题想了好久,最后怂了题解,又和身边同学商量一会儿才明白。。。
此题难点在于并不能正序求拓扑顺序,
因为当前选择了一个比较优的点但不能保证它接着找下去会优,
但是换个思维
开个大根堆
我们现在倒序存边时,当前取出的第一个点,这个点代表它是最大的值且他还需要一些条件才能实现
那就无条件把它放在最后输出(因为他是最不优的)
在每次拓扑时将每个top值计入下来,再拓扑后得到新点
每次得到的top值都是当前最差的点
最后倒叙述出就OK了
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<vector> 7 #include<string> 8 #include<queue> 9 #define MAXN 100700 10 #define ll long long 11 #define pt printf("---------\n"); 12 using namespace std; 13 priority_queue<int>q; 14 vector<int>chu[MAXN];int n,m; 15 int ru_du[MAXN],chu_du[MAXN]; 16 int D; 17 int ans[MAXN]; 18 int bian[MAXN]; 19 void work() 20 { 21 while(!q.empty()) 22 { 23 int top=q.top(); 24 q.pop(); 25 ans[++ans[0]]=top; 26 bian[top]=1; 27 for(int i=0;i<chu[top].size();++i) 28 { 29 int to=chu[top][i]; 30 if(bian[to]==1)continue; 31 ru_du[to]--; 32 if(ru_du[to]==0) 33 { 34 q.push(to); 35 } 36 } 37 } 38 return ; 39 } 40 int main() 41 { 42 scanf("%d",&D); 43 for(int k=1;k<=D;++k) 44 { 45 scanf("%d%d",&n,&m); 46 memset(bian,0,sizeof(bian)); 47 memset(ans,0,sizeof(ans)); 48 for(int i=1;i<=m;++i) 49 { 50 int x,y; 51 scanf("%d%d",&x,&y); 52 chu[y].push_back(x); 53 ru_du[x]++; 54 } 55 for(int i=n;i>=1;--i) 56 { 57 if(ru_du[i]==0) 58 { 59 q.push(i); 60 } 61 } 62 work(); 63 if(ans[0]!=n)printf("Impossible!\n"); 64 else 65 { 66 for(int i=ans[0];i>=1;--i) 67 { 68 printf("%d ",ans[i]); 69 } 70 printf("\n"); 71 } 72 for(int i=1;i<=n;++i) 73 {ru_du[i]=0;chu_du[i]=0;chu[i].clear();} 74 } 75 }View Code