题目传送门
【题目大意】
有$n$道菜和$m$个限制条件，对于第$i$个限制条件，编号为$x_i$的菜必须在编号为$y_i$的菜前面制作。求在保证满足所有限制条件的情况下，使得编号小的菜在尽量前面制作的排列方式。
【思路分析】
据说这题是拓扑排序常见套路？
好吧我来通俗一点讲一下
首先要意识到这题不是要字典序最小，而是要编号小的尽量在前面，那么我们反过来想就是编号大的要尽量在后面，把前面的位置留给编号小的，这是一个很显然的贪心策略
然后我们就考虑要倒序做了，那么如何满足限制呢？
我们可以把每个限制的$x,y$之间连一条边$y\to x$。因为要保证$y$在$x$的后面，那么倒序就相当于要保证$y$在$x$的前面，即先放了$y$之后再考虑放$x$。我们记录一个限制数目$d$，对于第$i$条限制$(x_i,y_i)$，我们在连完边之后，进行处理$d[x_i]++$，也就是说要在$d$的数目为0时才没有了限制，才能考虑放这个点。
为了完成编号大的要尽量在后面的要求，我们用一个大根堆来实现，如果当前这个点的$d$值为0，就插入大根堆。然后每次取出堆顶的元素记录答案，再沿着从这个点连出去的边，把每个连着的点$d$值减1，因为此时已经满足了限制。如果此时有$d$值为0的点，那么就再次插入大根堆。最后比较答案记录的个数和$n$的大小，若$n$大一些，则说明有些限制不可能满足，此时答案不存在；否则倒序输出记录的答案即为所求。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define g() getchar() 8 #define rg register 9 #define go(i,a,b) for(rg int i=a;i<=b;i++) 10 #define back(i,a,b) for(rg int i=a;i>=b;i--) 11 #define db double 12 #define ll long long 13 #define il inline 14 #define pf printf 15 #define mem(a,b) memset(a,b,sizeof(a)) 16 #define E(i,x) for(rg int i=head[x];i;i=e[i].next) 17 #define to(i) e[i].to 18 using namespace std; 19 int fr(){ 20 int w=0,q=1; 21 char ch=g(); 22 while(ch<'0'||ch>'9'){ 23 if(ch=='-') q=-1; 24 ch=g(); 25 } 26 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 27 return w*q; 28 } 29 const int N=100002; 30 int T,n,m,ed,head[N],d[N],ans[N]; 31 priority_queue<int> q;//用于把编号大的点排到前面,因为整个过程是倒序 32 struct edge{ 33 int to,next; 34 }e[N]; 35 il void build(rg int x,rg int y){ 36 e[++ed].next=head[x]; 37 e[ed].to=y;head[x]=ed; 38 d[y]++;//记录有几个限制 39 return; 40 } 41 il void work(){ 42 go(i,1,n) if(!d[i]) q.push(i);//先放没有限制的点 43 while(!q.empty()){ 44 rg int x=q.top();q.pop();//每次取出当前满足限制了的编号最大的点 45 ans[++ans[0]]=x;//记录答案 46 E(i,x){ 47 d[to(i)]--; 48 if(!d[to(i)]) q.push(to(i)); 49 } 50 } 51 if(ans[0]<n) {pf("Impossible!\n");return;} 52 //如果最后的数目不对,就相当于有限制条件无法满足 53 back(i,ans[0],1) pf("%d ",ans[i]);puts(""); 54 //倒序输出就是编号小的在前面了 55 return; 56 } 57 int main(){ 58 //freopen("","r",stdin); 59 //freopen("","w",stdout); 60 T=fr(); 61 while(T--){ 62 n=fr();m=fr(); 63 ed=0;mem(head,0);mem(d,0);mem(ans,0); 64 go(i,1,m){ 65 rg int x=fr(),y=fr(); 66 build(y,x);//有限制的话就连边,相当于我要先放好了y再考虑放x 67 } 68 work(); 69 } 70 return 0; 71 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11556886.html
