首页 > 代码库 > Bzoj2535 [Noi2010]Plane 航空管制2
Bzoj2535 [Noi2010]Plane 航空管制2
2535: [Noi2010]Plane 航空管制2
Time Limit: 10 Sec Memory Limit: 128 MBSec Special JudgeSubmit: 722 Solved: 456
Description
世博期间,上海的航空客运量大大超过了平时,随之而来的航空管制也频频发生。最近,小X就因为航空管制,连续两次在机场被延误超过了两小时。对此,小X表示很不满意。 在这次来烟台的路上,小 X不幸又一次碰上了航空管制。于是小 X开始思考关于航空管制的问题。 假设目前被延误航班共有 n个,编号为 1至n。机场只有一条起飞跑道,所有的航班需按某个顺序依次起飞(称这个顺序为起飞序列)。定义一个航班的起飞序号为该航班在起飞序列中的位置,即是第几个起飞的航班。 起飞序列还存在两类限制条件: ? 第一类(最晚起飞时间限制):编号为 i的航班起飞序号不得超过 ki; ? 第二类(相对起飞顺序限制):存在一些相对起飞顺序限制(a, b),表示航班 a的起飞时间必须早于航班 b,即航班 a的起飞序号必须小于航班 b 的起飞序号。 小X 思考的第一个问题是,若给定以上两类限制条件,是否可以计算出一个可行的起飞序列。第二个问题则是,在考虑两类限制条件的情况下,如何求出每个航班在所有可行的起飞序列中的最小起飞序号。
Input
第一行包含两个正整数 n和m,n表示航班数目,m表示第二类限制条件(相对起飞顺序限制)的数目。 第二行包含 n个正整数 k1, k2, „, kn。 接下来 m行,每行两个正整数 a和b,表示一对相对起飞顺序限制(a, b),其中1≤a,b≤n, 表示航班 a必须先于航班 b起飞。
Output
由两行组成。
第一行包含 n个整数,表示一个可行的起飞序列,相邻两个整数用空格分隔。
输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案,输出任
意一个即可。
第二行包含 n个整数 t1, t2, „, tn,其中 ti表示航班i可能的最小起飞序
号,相邻两个整数用空格分隔。
Sample Input
5 5
4 5 2 5 4
1 2
3 2
5 1
3 4
3 1
4 5 2 5 4
1 2
3 2
5 1
3 4
3 1
Sample Output
3 5 1 4 2
3 4 1 2 1
3 4 1 2 1
HINT
Source
鸣谢Benz
反向存边,并将每架飞机的起飞限制x改成n-x,就将问题转化成一个求飞机最晚起飞时间的问题,用拓扑排序可解。
如何求每架飞机的最小起飞次序? 在新问题中,每次限制不起飞某架飞机p,而将其他能飞的飞机都飞出去(拓扑排序时不处理p结点,让p连出去的边都保留下来),此时飞机p必须起飞了,这个时间就是它在新问题中的最晚起飞时间,也就是原问题中的最早起飞时间。
1 /************************************************************** 2 Problem: 2535 3 User: SilverN 4 Language: C++ 5 Result: Accepted 6 Time:1296 ms 7 Memory:3284 kb 8 ****************************************************************/ 9 10 #include<algorithm> 11 #include<iostream> 12 #include<cstring> 13 #include<cstdio> 14 #include<cmath> 15 #include<queue> 16 using namespace std; 17 const int mxn=30000; 18 int read(){ 19 int x=0,f=1;char ch=getchar(); 20 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 21 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 22 return x*f; 23 } 24 //bas 25 int n,m; 26 //plane 27 struct plane{ 28 int id; 29 int limit; 30 }p[mxn]; 31 int cmp(plane a,plane b){return a.limit<b.limit;} 32 //edge 33 struct edge{//存边,若a必须早于b起飞,则存一条从b到a的边 34 int v; 35 int nxt; 36 }e[mxn]; 37 int hd[mxn],mct=0; 38 void add_edge(int u,int v){ 39 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct; 40 return; 41 } 42 43 //拓扑排序 44 int limit[mxn]; 45 int ind[mxn]; 46 int top=0; 47 int ans[mxn]; 48 int deg[mxn]; 49 /* 50 queue<int>q; 51 void solve(int x){ 52 memcpy(deg,ind,sizeof ind); 53 while(!q.empty()) q.pop(); 54 int i,j; 55 top=0; 56 int pos=1; 57 for(i=1;i<=n;i++){ 58 for(;pos<=n && p[pos].limit<i;pos++){ 59 int v=p[pos].id; 60 if(!deg[v] && x!=v){ 61 q.push(v); 62 ans[++top]=v; 63 } 64 } 65 if(q.empty())break; 66 int u=q.front();q.pop(); 67 for(j=hd[u];j;j=e[j].nxt){ 68 int v=e[j].v; 69 deg[v]--; 70 if(!deg[v] && v!=x && limit[v]<i){ 71 q.push(v); 72 ans[++top]=v; 73 } 74 } 75 } 76 return; 77 }*/ 78 int head,tail; 79 int q[mxn<<3]; 80 void solve(int x){//不安排x 81 int pos,i,j,u,v; 82 memcpy(deg,ind,sizeof ind); 83 head=tail=0; 84 for(i=1,pos=1;i<=n;i++){ 85 for(;pos<=n && p[pos].limit<i;pos++){ 86 int v=p[pos].id; 87 if(!deg[v] && x!=v){ 88 // printf("test2:%d %d\n",deg[v],v); 89 q[++tail]=v; 90 } 91 } 92 if(head<tail){ 93 u=q[++head]; 94 for(j=hd[u];j;j=e[j].nxt){ 95 int v=e[j].v; 96 deg[v]--; 97 if(!deg[v] && v!=x && limit[v]<i){ 98 // printf("test3:%d %d\n",deg[v],v); 99 q[++tail]=v;100 }101 }102 }103 else return;104 }105 return;106 }107 108 //main109 int main(){110 int i,j;111 n=read();m=read();112 for(i=1;i<=n;i++){113 p[i].limit=read();114 p[i].limit=n-p[i].limit;115 p[i].id=i;116 limit[i]=p[i].limit;117 }118 int u,v;119 sort(p+1,p+n+1,cmp);120 for(i=1;i<=m;i++){121 u=read();v=read();122 ind[u]++;123 add_edge(v,u);124 }125 solve(0);126 for(i=tail;i;i--)printf("%d ",q[i]);127 // for(i=top;i;i--)printf("%d ",ans[i]);128 printf("\n");129 for(i=1;i<=n;i++){130 solve(i);131 printf("%d ",n-tail);132 }133 return 0;134 }
Bzoj2535 [Noi2010]Plane 航空管制2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。