洛谷P3243 [HNOI2015]菜肴制作 题解

题目链接：洛谷P3243 [HNOI2015]菜肴制作 题解

题意： $t$ 组数据，每组要做 $n$ 个菜，但是需要满足 $m$ 个限制。

每个限制形如 $(i,j)$ ，指菜肴 $i$ 要在菜肴 $j$ 之前做。（这里的 $i,j$ 都是编号）

在满足所有限制的前提下，要保证编号越小的菜肴越早做。

对于每组数据，求出最优的菜肴制作顺序，或者输出 Impossible! 表示无解

$m$ 条限制中可能存在完全相同的。

$1\le t \le 3,~ 1 \le n,m \le 10^5$

显然建图然后topo，有环就无解。

但是怎么拓扑呢？字典序最小？

显然，这并不显然是错的

例： $(2,4),~(3,1)$

字典序最小的算出来的是 2,3,1,4 ，而答案是 3,1,2,4

原因在于字典序最小，不一定能保证 $1$ 尽可能在前面

即字典序最小，不一定保证编号越小的菜肴越早做

重新考虑怎么做

题目要求编号越小的菜肴越早做

因此标号越大的菜肴就要越晚做

则每个菜肴在它的合法范围内一定是放到最后面时最优

于是考虑建反图求字典序最大的拓扑序

时间复杂度 $O(tn)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e5+15)

int n,m,pos=1,head[N],in[N],ans[N];
struct Edge{int u,v,next;} e[N];
priority_queue<int> q;
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos; ++in[v];
}
void topo()
{
    for(int i=n; i>=1; i--)
        if(!in[i]) q.push(i);
    int cnt=0;
    while(!q.empty())
    {
        int u=q.top(); q.pop();
        ans[n-(++cnt)+1]=u;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            if(!(--in[v])) q.push(v);
        }
    }
    if(cnt!=n) return puts("Impossible!"),void(0);
    for(int i=1; i<=n; i++)
        write(ans[i]),pc(" \n"[i==n]);
}
void clear()
{
    pos=1;
    for(int i=1; i<=n; i++)
        head[i]=in[i]=0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; read(Q);
    while(Q--)
    {
        clear(); read(n); read(m);
        for(int i=1,u,v; i<=m; i++)
        {
            read(u); read(v);
            addEdge(v,u);
        } topo();
    }
    return 0;
}