解题：NOI 2010 航空管制

题面

常见的套路与不常见的套路

第一问是常见的套路，建反边用优先队列跑拓扑排序

第二问是不常见的套路，如何判断一个点最早什么时候起飞？先不加它来拓扑排序，直到拓扑排序不能进行下去了，这个时刻就是它必须加入的时刻。因为我们是反着做的，所以这样求出来的就是最早时刻。

 // luogu-judger-enable-o2

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=;

 int n,m,t1,t2,cnt,top;

 int p[N],noww[M],goal[M];

 int mem[N],deg[N],lst[N],stk[N],que[N];

 priority_queue<pair<int,int> > hp;

 void Clean()

 {

     priority_queue<pair<int,int> > tmp;

     swap(hp,tmp);

 }

 void Link(int f,int t)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,mem[t]++;

 }

 int Solve(int nde)

 {

     Clean();

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

         if(!(deg[i]=mem[i])&&i!=nde)

             hp.push(make_pair(lst[i],i));

     deg[nde]=n;

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

     {

         if(hp.empty()) return i;

         pair<int,int> tn=hp.top(); hp.pop();

         if(tn.first<i) return i;

         for(int i=p[tn.second];i;i=noww[i])

             if(!(--deg[goal[i]]))

                 hp.push(make_pair(lst[goal[i]],goal[i]));

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

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

         scanf("%d",&lst[i]);

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

         scanf("%d%d",&t1,&t2),Link(t2,t1);

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

         if(!(deg[i]=mem[i])) hp.push(make_pair(lst[i],i));

     while(!hp.empty())

     {

         pair<int,int> tn=hp.top();

         hp.pop(),stk[++top]=tn.second;

         for(int i=p[tn.second];i;i=noww[i])

             if(!(--deg[goal[i]]))

                 hp.push(make_pair(lst[goal[i]],goal[i]));

     }

     while(top) printf("%d ",stk[top--]); puts("");

     for(int i=;i<=n;i++) printf("%d ",Solve(i));

     return ;

 }