BZOJ 2535：NOI 2010 航空管制

[NOI2010]航空管制

题面请点上面。

首先第一问，我第一想法是把它放到一个小根堆中，然而这是不行的。

正确的思路是，把图反过来建，然后放到一个大根堆里去。

至于原因，感性理解一下，正着贪是有后效性，会陷入到局部最优解，而反着贪则是从终点出发，是正确的。

第二问也不难，我们考虑当前这个点，能不动他就不动，直到不动不行了（此时两种情况，一是堆空了，二是有人起飞时间晚于降落时间），此时就是第二问的答案。

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cmath>

#include<queue>

#define SIZE 1000005

#define rint register int

using namespace std;

inline int read()

{

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

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;

    for(;isdigit(ch);ch=getchar()) x=x*+ch-'';

    return x*f;

}

inline void write(int x)

{

    if(x<) putchar('-'),x=-x;

    if(x>) write(x/);

    putchar(x%+'');

    return ;

}

struct node

{

    int id,v;

    bool operator < (const node &x) const

    {

        return x.v>v;

    }

};

int n,m,cnt,in[SIZE],ru[SIZE],ans[SIZE],v[SIZE];

int head[SIZE],nex[SIZE],to[SIZE],total;

priority_queue<node> q;

inline void link(int x,int y)

{

    to[++total]=y;

    nex[total]=head[x];

    head[x]=total;

    return ;

}

inline void solve1()

{

    for(rint i=;i<=n;++i) in[i]=ru[i];

    for(rint i=;i<=n;++i)

        if(!in[i])

            q.push((node){i,v[i]});

    while(q.size())

    {

        int x=q.top().id;q.pop();

        ans[++cnt]=x;

        for(rint i=head[x];i;i=nex[i])

        {

            int y=to[i];--in[y];

            if(!in[y]) q.push((node){y,v[y]});

        }

    }

}

inline int solve2(int k)

{

    while(q.size()) q.pop();

    for(rint i=;i<=n;++i) in[i]=ru[i];

    for(rint i=;i<=n;++i)

        if(!in[i] && i!=k)

            q.push((node){i,v[i]});

    for(rint c=n;c>=;--c)

    {

        if(!q.size() || q.top().v<c) return c;

        int x=q.top().id;q.pop();

        for(rint i=head[x];i;i=nex[i])

        {

            int y=to[i];--in[y];

            if(!in[y] && y!=k) q.push((node){y,v[y]});

        }

    }

}

int main()

{

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

    for(rint i=;i<=n;++i) v[i]=read();

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

    {

        int x=read(),y=read();

        link(y,x);++ru[x];

    }

    solve1();

    for(rint i=cnt;i>=;--i) write(ans[i]),cout<<" ";puts("");

    for(rint i=;i<=n;++i) write(solve2(i)),cout<<" ";

    return ;

}