【[NOI2010]航空管制】

关于拓扑排序的反建图还是一个非常套路的东西

比如说[HNOI2015]菜肴制作

我们希望使得某一个东西在拓扑序中出现的尽可能早，这个时候就可以建出一张反图来，使得这个东西在反图中的拓扑序尽量靠后，从而使得其出现的尽可能地早

这是为什么呢，比如说我们希望\(1\)出现的尽可能早，直接在正图上开一个小根堆来进行拓扑排序显然错的

为什么呢，因为这样只能使字典序尽可能小，而不是使得\(1\)尽可能靠前

但是我们建出反图来呢，显然反图上按照上述方法来跑的话会使得反向字典序最小，而最小的反向字典序一定是\(1\)最靠后的

这道题可以建出一个反图来，从而使得限制条件变成了每一个航班在拓扑序中的位置\(>n-k[i]\)，于是我们直接用小根堆来维护\(n-k[i]\)就好了

至于第二问，在每一个点入度为\(0\)可以进堆的时候，我们先不让它进去，而是等某一个元素不满足条件的时候，这个时候就是应该进堆了

代码

#include<iostream>

#include<queue>

#include<cstdio>

#include<cstring>

#define re register

#define mp std::make_pair

#define maxn 2005

struct E

{

    int v,nxt;

}e[10005];

int head[maxn],r[maxn],d[maxn];

int c[maxn];

int ans[maxn],tot;

int n,m,num;

typedef std::pair<int,int> pii;

std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;

inline void add_edge(int x,int y)

{

    e[++num].v=y;

    e[num].nxt=head[x];

    head[x]=num;

}

inline int read()

{

    char c=getchar();

    int x=0;

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9')

        x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x;

}

inline int work(int x)

{

    tot=0;

    while(!q.empty()) q.pop();

    for(re int i=1;i<=n;i++) r[i]=c[i];

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

    if(!r[i]) q.push(mp(n-d[i],i));

    while(!q.empty())

    {

        int k=q.top().second;

        q.pop();

        if(k==x) continue;

        if(n-tot>d[k]) return n-tot;

        tot++;

        for(re int i=head[k];i;i=e[i].nxt)

        {

            r[e[i].v]--;

            if(!r[e[i].v]) q.push(mp(n-d[e[i].v],e[i].v));

        }

    }

    return n-tot;

}

int main()

{

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

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

        d[i]=read();

    int x,y;

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

        x=read(),y=read(),add_edge(y,x),r[x]++;

    for(re int i=1;i<=n;i++) c[i]=r[i];

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

        if(!r[i]) q.push(mp(n-d[i],i));

    while(!q.empty())

    {

        int k=q.top().second;

        q.pop();

        ans[++tot]=k;

        for(re int i=head[k];i;i=e[i].nxt)

        {

            r[e[i].v]--;

            if(!r[e[i].v]) q.push(mp(n-d[e[i].v],e[i].v));

        }

    }

    for(re int i=n;i;i--)

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

    puts("");

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

        printf("%d ",work(i));

    return 0;

}

巴特西

【[NOI2010]航空管制】

最新文章

热门文章