菜肴制作-题解

查看原题请戳这里

一道明目张胆的拓扑排序的题目

首先，由于题目给出“某些菜肴必须在另一些菜肴之前制作”这一条件，所以这道题可以用拓扑去做。
其次，根据题目给出的“最优的菜肴制作顺序”的定义，我们自然而然的想到题目是让我们求字典序最小的拓扑序。

然而，这样做事错误的。

出题人可以轻松把你卡掉，比如样例的第三组数据，答案是1 5 2 4 3，但是如果你是求的字典序最小的拓扑序，那么你求出的结果将会是1 4 3 5 2。很显然，2的位置靠后了。

既然求最小的字典序行不通，那么我们是不是可以反过来想呢？

由于题目要求你把小的数尽量往前放，所以答案不一定是最小的字典序。但是，把小的数尽量往前方，那么大的数自然会尽量往后，这样一来，如果把拓扑序反过来，那么字典序最大的反拓扑序就一定是最优解。于是，我们可以建一个返图去求字典序最大的拓扑序，最后再倒序输出。 tip：为了优化时间复杂度，我们可以用堆去进行拓扑排序。 附一下代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define INF 0x7fffffff

using namespace std;
priority_queue<int>que;
int t,n,m,x,cnt,d[100005],k[100005],ans[100005];
struct Edge{
    int to,next;
}edge[100005];
struct node{
    int x,y;
}u[100005];
void add(int x,int y)
{
    edge[++cnt].to = y;
    edge[cnt].next = d[x];
    d[x] = cnt;
    k[y] ++;
}
int mysort(node a,node b) {return a.y < b.y;}
void clean()
{
    while(!que.empty()) que.pop();
}
void work()
{
    for(register int i = 1; i <= n; i++) if(k[i] == 0) que.push(i);
    while(!que.empty())
    {
        x = que.top();
        ans[++cnt] = x;
        que.pop();
        for(register int i = d[x]; edge[i].to != 0; i = edge[i].next)
        {
            k[edge[i].to] –;
            if(k[edge[i].to] == 0) que.push(edge[i].to);
        }
    }
}
int main()
{
    scanf(“%d”,&t);
    for(register int a = 1; a <= t; a++)
    {
        cnt = 0;
        memset(d,0,sizeof(d));
        memset(k,0,sizeof(k));
        clean();
        scanf(“%d%d”,&n,&m);
        for(register int i = 1; i <= m; i++) scanf(“%d%d”,&u[i].x,&u[i].y);
        for(register int i = 1; i <= m; i++) add(u[i].y,u[i].x);
        cnt = 0;
        work();
        if(cnt < n) printf(“Impossible!”);
        else
        for(register int i = n; i >= 1; i–) printf(“%d “,ans[i]);
        printf(“\n”);
    }
    return 0;
}