「HNOI 2015」菜肴制作

题目链接

戳我

\(Description\)

有若干限制,需要求一个\(1\)到\(n\)的排列,每个限制\((x,y)\)表示\(x\)必须在\(j\)之前,并要求所求的排列满足所有限制并让\(1\)的位置尽量靠前,在此基础上让\(2\)的位置尽量靠前,以此类推.

\(n<=100000\)

\(Solution\)

这题直接拓扑排序选字典序最小的显然不行,因为题目要求不是问字典序最要,而是要:

满足所有限制并让\(1\)的位置尽量靠前,在此基础上让\(2\)的位置尽量靠前,以此类推

那么我们显然需要想一想别的办法了.

那么想一想,怎么样满足条件呢?

如果把越大的数放在后面，那么前面的小数都能够尽量靠前。

这样便符合条件了

至于做法:

建反向图用堆跑拓扑排序,每次取出入度为\(0\)且最大的点.

最后反序输出就好了.

\(Code\)

#include<bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;

int read() {

    int x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();

    return x*f;

}

priority_queue<int> q;

struct node {

    int to,next;

}a[100010<<1];

int head[100010],cnt,vis[100010],ans[100010];

void add(int x,int y){

    a[++cnt].to=y;

    a[cnt].next=head[x];

    head[x]=cnt;

}

void solve(){

    memset(vis,0,sizeof(vis)),memset(head,0,sizeof(head)),cnt=0;

    int n=read(),m=read(),x,y,v,tot=0;

    for(int i=1;i<=m;i++)

        x=read(),y=read(),add(y,x),vis[x]++;

    for(int i=1;i<=n;i++)

    if(!vis[i])

        q.push(i);

    while(!q.empty()){

        int now=q.top();

        q.pop();

        for(int i=head[now];i;i=a[i].next){

            v=a[i].to,vis[v]--;

            if(!vis[v])

            q.push(v);

        }

        ans[++tot]=now;

    }

    if(tot!=n)

        puts("Impossible!");

    else{

        for(int i=n;i>=1;i--)

            printf("%d ",ans[i]);

        printf("\n");

    }

}

main(){

    int T=read();

    while(T--)

        solve();

}