首页 > 代码库 > BZOJ2109 NOI2010 Plane 航空管制 拓扑排序
BZOJ2109 NOI2010 Plane 航空管制 拓扑排序
题意：给定两种限制：1、编号为i的航班必须在ki+1之前起飞 2、(a,b)表示a必须在b之前起飞。求：1、一个合法起飞序列 2、每个航班在所有合法起飞顺序中，最早的起飞时间。问题保证有解
题解：首先按照第二个限制条件建图，那么第一问随便跑一个拓扑序就好，关键在第二问，我们枚举每一个飞机，假定该飞机不存在，不断往拓扑序中加点，直到没法再加点（不存在一个空的位置t满足存在一个节点i满足t∈[N-ki+1,N]）为止，这样求出来的位置就是答案。
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=2000+2;const int MAXM=10000+2;struct NODE{ int u,k;}node[MAXN];struct HASH{ int v; HASH *next; HASH(){} HASH(int _v,HASH *_next):v(_v),next(_next){}}*table[MAXN],mem[2*MAXM];int N,M,k[MAXN],degree[MAXN],d[MAXN],cnt,q[MAXN],s,t;bool cmp(NODE x,NODE y){ return x.k<y.k;}void Insert(int u,int v){ table[u]=&(mem[cnt++]=HASH(v,table[u]));}void Topological_Sort(int u){ memcpy(d,degree,sizeof(degree)); s=t=0; for(int i=1,j=1;i<=N;i++){ for(;j<=N && node[j].k<i;j++) if(!d[node[j].u] && node[j].u!=u) q[t++]=node[j].u; if(s<t) for(HASH *p=table[q[s++]];p;p=p->next){ d[p->v]--; if(!d[p->v] && p->v!=u && k[p->v]<i) q[t++]=p->v; } else return; }}int main(){ scanf("%d %d",&N,&M); for(int i=1;i<=N;i++){ scanf("%d",&node[i].k); node[i].u=i,k[i]=node[i].k=N-node[i].k; } sort(node+1,node+N+1,cmp); for(int i=1,u,v;i<=M;i++){ scanf("%d %d",&u,&v); Insert(v,u),degree[u]++; } Topological_Sort(-1); for(int i=N-1;i>=0;i--){ printf("%d",q[i]); if(!i) printf("\n"); else printf(" "); } for(int i=1;i<=N;i++){ Topological_Sort(i); printf("%d ",N-t); } return 0;}
BZOJ2109 NOI2010 Plane 航空管制 拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。