【】

【分析】真的是一道贪心好题。开始我以为是一道大水题。建立拓扑图后（没环就是方便！），直接把最外层设定序号为1，第二层为2，bfs下去即可。。。结果发现：飞行序号不能相同。。。于是开始想。

先考虑第一个问题：打印一个合法序列。我开始是这么想的：

观察每个飞机的最晚飞行序号Ki，因为必定有解，所以我们可以让它的序号就是Ki。然后用它的时间去更新前面的时间（图可以反向建立）。应该可以维护一个大根堆，每次挑出最大的一个进行处理。

【简易代码】

  memset(T,0x7f,sizeof(T));
  for (i=1;i<=n;i++)
    if (!num[i]) T[i]=k[i],q.push(make_pair(k[i],i));
  while (!q.empty())
  {
    temp=q.top();q.pop();
    P=temp.second;
    for (i=end[P];i;i=a[i].next)
    {
      go=a[i].go;
      if (T[P]-1
  
   


   
考虑第二个问题：求出每个飞机最早的起飞序列。好像嘛，有点~~

   
我是这么想的：每次枚举一架飞机i,先找到所有在它之前的飞机（以下的dfs进行了一遍flood―fill）

   
显然这些是一定在前面的。然后我再去找剩余的飞机――统计最晚时间ki的个数。然后枚举可行的时间点j并判断是否可行（二分也可以，不过反正已经O(N)了）。

   
【简易代码】

   

   
 for (now=1;now<=n;now++)
  {
    memset(T,0,sizeof(T));
    memset(deep,0,sizeof(deep));
    dfs(now);
    ans=sum=0;
    for (i=1;i<=n;i++)
      if (T[i]&&i!=now) ans++;else if (i!=now) deep[k[i]]++;
    //for (i=1;i<=k[now];i++) sum+=deep[i];
    for (i=1;i<=k[now];i++)
    {
      if (ans+sum
    
     


     
【思考】啦啦啦~~~可惜，以上的想法都是错的。。。。

     
第二个有点想通了，因为ki的限制，有些飞机的最晚时间可能的确大于j，但是他们必须立刻起飞，否则就没有时间了。我跑出来的解和标准数据相差的不是很大，可以当骗分用。

     
【正解】膜拜了VLK的题解――可以把所有的边反向，ki与N取反。这样，最晚时间变成了最早时间，也就是说，枚举到每个点的时候，都可以尽可能的拖晚时间。

     
【AC代码】

     

     
#include
      
       
#include
       
         #include
        
          #include
         
           #define N 2005 using namespace std; struct arr{int go,next;}a[20005]; int end[N],ord[N],T[N],k[N],dis[N],num[N],id[N],Q[N]; int P,n,m,i,x,y,now,cnt,go,ans,sum; pair
          
           temp; inline void add(int u,int v) { a[++cnt].go=v;a[cnt].next=end[u];end[u]=cnt; } inline int work(int x) { memcpy(dis,num,sizeof(num)); int h=0,t=0,v,p,i; for (i=p=1;i<=n;i++) { for (;p<=n&&k[v=ord[p]]
           
            1) printf(" ");else printf("\n"); } for (i=1;i<=n;i++) printf("%d ",n-work(i)); return 0; }
           
          
         
        
       
      
     


     
【总结】一道NOI的好题，有时间值得再次回顾！