题目描述
知名美食家小A被邀请至ATM大酒店,为其品评菜肴。
ATM酒店为小A准备了道菜肴,酒店按照为菜肴预估的质量从高到低给予
到
的顺序编号,预估质量最高的菜肴编号为
。由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有
条形如“
号菜肴必须先于
号菜肴制作”的限制,我们将这样的限制简写为
。现在,酒店希望能求出一个最优的菜肴的制作顺序,使得小A能尽量先吃到质量高的菜肴。也就是说
1.在满足所有限制的前提下,
号菜肴“尽量”优先制作;
2.在满足所有限制,
号菜肴“尽量”优先制作的前提下,
号菜肴“尽量”优先制作;
3.在满足所有限制,
号和
号菜肴“尽量”优先的前提下,
号菜肴“尽量”优先制作;
4.在满足所有限制,
号和
号和
号菜肴“尽量”优先的前提下,
号菜肴“尽量”优先制作;
5.以此类推。
现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!” (不含引号,首字母大写,其余字母小写)
输入格式
第一行是一个正整数D,表示数据组数。
接下来是D组数据。对于每组数据:
第一行两个用空格分开的正整数和
,分别表示菜肴数目和制作顺序限制的条目数。
接下来行,每行两个正整数
,表示“
号菜肴必须先于
号菜肴制作”的限制。
注意:条限制中可能存在完全相同的限制。
输出格式
输出文件仅包含行,每行
个整数,表示最优的菜肴制作顺序,或者”Impossible!”表示无解(不含引号)。
题目解析
这样的题怎么就轻易地HNOI了呢……(但其实还是有坑点的~)
拓扑排序,但不是字典序最小。
注意到我们可以将图中所有边反向,每次取出入度为0的编号最大的点。这样我们就可以保证编号小的尽量在后面。
最后倒序输出就好啦。时间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
/************************************************************** Problem: 4010 User: frank_c1 Language: C++ Result: Accepted Time:804 ms Memory:3612 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct edge { int next,to; }; const int maxn=(int)(1e5)+5; int fr[maxn]; int s[maxn]; int in[maxn]; edge e[maxn]; int T,tote=0; priority_queue<int> Q; inline void addedge(int u,int v) { ++tote;e[tote].next=fr[u];fr[u]=tote;e[tote].to=v; } void solve() { memset(fr,-1,sizeof(fr)); memset(in,0,sizeof(in)); int n,m;tote=0; read(n);read(m); REP(i,1,m) { int u,v; read(u);read(v); addedge(v,u);++in[u]; } int cnt=0; REP(i,1,n) if(!in[i]) Q.push(i); while(!Q.empty()) { int x=Q.top();Q.pop();s[++cnt]=x; RAL(i,x) if(--in[e[i].to]==0) Q.push(e[i].to); } if(cnt!=n) printf("Impossible!"); else PER(i,n,1) printf("%d ",s[i]); putchar('\n'); } int main() { read(T); while(T--) solve(); return 0; } |