首页 > 代码库 > Bzoj2535 [Noi2010]Plane 航空管制2

Bzoj2535 [Noi2010]Plane 航空管制2

 

2535: [Noi2010]Plane 航空管制2

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 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

Sample Output

3 5 1 4 2
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