tarjan缩点+拓扑排序 BZOJ2535 [Noi2010]Plane 航空管制

2535: [Noi2010]Plane 航空管制2

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 818  Solved: 517
[Submit][Status][Discuss]

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

题目描述已经提示正解了，此题要反向存。

存边，并将每架飞机的起飞限制x改成n-x，就将第一问转化成一个求飞机最晚起飞时间的问题，用拓扑排序可解。
第二问：每次限制不起飞某架飞机p，而将其他能飞的飞机都飞出去（拓扑排序时不处理p结点，让p连出去的边都保留下来），此时飞机p必须起飞了，这个时间就是它在新问题中的最晚起飞时间，也就是原问题中的最早起飞时间。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,cnt,hd,tl;
struct data{
    int limit,num;
}p[2010];
struct dt{
    int nex,to;
}edge[20010];
int lim[2010],getin[2010],gtin[2010],head[2010],q[2010];
bool cmp(const data&aa,const data&bb){
    return aa.limit<bb.limit;
}
void add(int start,int end){
    edge[++cnt].nex=head[start];
    edge[cnt].to=end;
    head[start]=cnt;
}
void work(int x){
    memcpy(gtin,getin,sizeof(getin));
    hd=tl=0;//!!!
    for(int t=1,i=1;i<=n;i++){
        /*for(int t=1;t<=n;t++)
            if(p[t].limit<i&&!gtin[p[t].num]&&x!=p[t].num) q[++tl]=p[t].num;*/
        for(;t<=n&&p[t].limit<i;t++)
            if(!gtin[p[t].num]&&p[t].num!=x) q[++tl]=p[t].num;  
        if(hd<tl){
            int u=q[++hd];
            for(int j=head[u];j;j=edge[j].nex){
                gtin[edge[j].to]--;
                if(!gtin[edge[j].to]&&x!=edge[j].to&&lim[edge[j].to]<i) q[++tl]=edge[j].to;
            }
        }
        else return;
    }       
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i].limit);
        p[i].limit=n-p[i].limit;
        p[i].num=i;
        lim[i]=p[i].limit;
    }
    sort(p+1,p+n+1,cmp);
    int a,b;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        getin[a]++;
        add(b,a);
    }
    work(0);
    for(int i=tl;i>=2;i--) printf("%d ",q[i]);
    printf("%d
",q[1]);
    for(int i=1;i<n;i++){
        work(i);
        printf("%d ",n-tl);
    }
    work(n);
    printf("%d",n-tl);
    return 0;
}