P3243 [HNOI2015]菜肴制作

传送门

把时间看成数，菜肴看成位置

考虑一个位置填什么数很麻烦

考虑一个数放在什么位置

一开始我想的是，对于一个限制 $(a,b)$ ，从 $a$ 往 $b$ 连一条边，然后如果有解则所有的限制构成了一个 $DAG$

考虑当前最小的数给谁，显然是当前没有入度的且编号最小的点

所以可以直接按拓扑序把数一个个 '给' 过去，并用升序的优先队列维护当前没有入度的位置最小的点

然后就 $GG$ 了

随手一个数据就可以 $hack$ 掉：

$4\ 2$

$1\ 3$

$4\ 2$

正确答案：1 3 4 2，错误输出：1 4 2 3

考虑一下为什么会 $GG$

一开始 $1,4$ 没有入度，队列中： $1,4$

把 $1$ 取出来，然后 $3$ 也没有入度，队列中 $3,4$

把 $3$ 取出来，队列中 $4$

把 $4$ 取出来，$2$ 没有入度，队列中 $2$

把 $2$ 取出来，结束

分析一下问题出在哪，$4$，指向一个小于 $3$ 的节点$2$，如果先把 $4$ 取走，那么 $2$ 的编号就会比较小

就是说，一开始数 $a$ 给了位置 $p$，然后 $a+1$ 给位置 $pr,(pr>p)$，然后因为 $pr$ 有一条边连给 $pl,(pl<p)$，所以 $a+2$ 给 $pl$，导致 $GG$

考虑反过来，把 $DAG$ 反过来，最大值先 '给' 位置最大的数，用降序优先队列维护当前没有入度的位置最大的点

这样就可以避免出现这种情况

然后就可以了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

#include<queue>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e5+;

int n,m,cnt[N],pos[N],ans[N],now;

vector <int> v[N];

priority_queue <int> q;

int main()

{

    int T=read();

    while(T--)

    {

        n=read(),m=read();

        for(int i=;i<=n;i++) cnt[i]=pos[i]=ans[i]=,v[i].clear();

        int a,b;

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

        {

            a=read(),b=read();

            v[b].push_back(a); cnt[a]++;

        }

        for(int i=;i<=n;i++) if(!cnt[i]) q.push(i);

        now=n;

        while(!q.empty())

        {

            int x=q.top(); pos[x]=now--; q.pop();

            for(int i=v[x].size()-;i>=;i--)

            {

                cnt[v[x][i]]--;

                if(!cnt[v[x][i]]) q.push(v[x][i]);

            }

        }

        bool flag=;

        for(int i=;i<=n;i++) if(!pos[i]) { printf("Impossible!\n"); flag=; break; }

        if(!flag) continue;

        for(int i=;i<=n;i++) ans[pos[i]]=i;

        for(int i=;i<=n;i++) printf("%d ",ans[i]); printf("\n");

    }

    return ;

}

巴特西

P3243 [HNOI2015]菜肴制作

最新文章

热门文章