P3243 [HNOI2015]菜肴制作

2018-09-13 16:42:47


首先,有做菜的先后顺序,是一个拓扑排序

题目用了一大段话让你相信这是求字典序最小的排列

然而好像并不对,举个栗子:

$4$ 种菜肴,限制为 $<2,4><3,1>$

字典序最小的排列是 $2,3,1,4$ ,而正解应该是 $3,1,2,4$

因为编号小的要尽量靠前


那么如何拓扑排序才是正确的呢?

从上面的栗子可以看出,把较大的数放在尽量靠后的位置,可以使较小的数尽量靠前

所以转换一个角度

建出反图,求出字典序最大的拓扑序,这样较大的数在靠前的位置

反过来输出就是要求的答案了。

别忘了 $Impossible$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
#define reset(a) memset(a,0,sizeof(a))
using namespace std;
const int N=1e5+5;
struct node
{
    int to,nxt;
}edge[N];
int T,n,m,num,cnt,head[N],d[N],ans[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
inline void topsort()
{
    priority_queue<int>q;
    for (reg int i=1;i<=n;i++)
      if (!d[i]) q.push(i);
    while (!q.empty())
    {
        int u=q.top(); q.pop();
        ans[cnt--]=u;
        for (reg int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if (!--d[v]) q.push(v);
        }
    }
}
int main()
{
    T=read();
    while (T--)
    {
        n=read(),m=read(); num=0; reset(ans);
        reset(head); reset(edge); reset(d); cnt=n;
        for (reg int i=1;i<=m;i++)
        {
            int x=read(),y=read();
            add_edge(y,x); ++d[x];
        }
        topsort();
        if (cnt) puts("Impossible!");
        else
        {
            for (reg int i=1;i<=n;i++) printf("%d ",ans[i]);
            putchar(10);
        }
    }
    return 0;
}