题解：P3243 [HNOI2015] 菜肴制作

rq_hyj · 2024-12-24 20:48:33 · 题解

做法

首要想到字典序最小的拓扑序，发现题目要求的是数字小的尽量靠前，so 打开题解 略微思索一二，发现当大的数尽量靠后，那么小的数也会尽量靠前。所以反向建图跑字典序最大的拓扑序！！! 过于巧妙！！！

代码：

#include<cstdio>
#include<queue>
#include<stack>
using namespace std;
int len;
int n,m;
int a,b;
int in[100005];
int num[100005],pre[100005],last[100005],cnt;
priority_queue <int> q;
stack <int> ans;
void ddxyz(){
    cnt=0;
    while(!q.empty()){
        q.pop();
    }
    while(!ans.empty()){
        ans.pop();
    }
    for(int i=1;i<=100000;i++){
        in[i]=num[i]=pre[i]=last[i]=0;
    }
}
void add(int x,int y){
    ++cnt;
    num[cnt]=y;
    pre[cnt]=last[x];
    last[x]=cnt;
}
void tp(){
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            q.push(i);
        }   
    }
    while(!q.empty()){
        int fro=q.top();
        q.pop();
        ans.push(fro);
        for(int i=last[fro];i;i=pre[i]){
            in[num[i]]--;
            if(in[num[i]]==0){
                q.push(num[i]);
            }
        }
    }
}
int main(){
    scanf("%d",&len);
    while(len--){
        ddxyz();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            add(b,a);
            in[a]++;
        } 
        tp();
        if(ans.size()<n){
            printf("Impossible!\n");
        } 
        else{
            while(!ans.empty()){
                printf("%d ",ans.top());
                ans.pop();
            }
            printf("\n");
        }
    }
    return 0;
}