NOI2010 航空管制

题目:

   世博期间,上海的航空客运量大大超过了平时,随之而来的航空管制也频频发生。最近,小X就因为航空管制,连续两次在机场被延误超过了两小时。
   对此,小X表示很不满意。 在这次来烟台的路上,小X不幸又一次碰上了航空管制。于是小X开始思考关于航空管制的问题。
   假设目前被延误航班共有n个,编号为1至n。机场只有一条起飞跑道,所有的航班需按某个顺序依次起飞(称这个顺序为起飞序列)。定义一个航班的起飞序号为该航班在起飞序列中的位置,即是第几个起飞的航班。
   起飞序列还存在两类限制条件:
   第一类(最晚起飞时间限制):编号为i的航班起飞序号不得超过ki;
   第二类(相对起飞顺序限制):存在一些相对起飞顺序限制(a, b),表示航班a的起飞时间必须早于航班b,即航班a的起飞序号必须小于航班b的起飞序号。
   小X思考的第一个问题是,若给定以上两类限制条件,是否可以计算出一个可行的起飞序列。
   第二个问题则是,在考虑两类限制条件的情况下,如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

思路:

   如果把每架飞机的真实起飞时间限制 定为它自身的最晚起飞时间的必须在它之后起飞的飞机最晚起飞时间 的最小值,那么把所有飞机按照 排序就能得到第一问的合法解。
   设 表示 小于等于 的飞机个数,那么就能算出 表示前 个时刻有多少不受限制的位置。如果要把 的起飞时间改为 ,那所有必须在 之前起飞的飞机的时间都必须小于 ,那么受影响的点其实只有那些 的点,求出这些点的个数为 。那么只要满足 就行了。

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 2005, M = 10005;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int k) {return W[k];}
};
Link<N, M, int> G, F;

int n, m;
int lim[N];
bool vis[N];

void dfs(int o) {
    if(vis[o]) return;
    vis[o] = true;
    erep(k, G, o) {
        int v = G[k];
        dfs(v);
        tomin(lim[o], lim[v] - 1);
    }
}

void dfsF(int o) {
    if(vis[o]) return;
    vis[o] = true;
    erep(k, F, o) dfsF(F[k]);
}

bool cmp(int a, int b) {
    return lim[a] < lim[b];
}

int id[N], cnt[N], ned[N], vec[N], scnt[N], pos[N];
int main() {
    File(plane);
    scanf("%d%d", &n, &m);
    rep(i, 1, n) scanf("%d", lim + i);
    rep(i, 1, m) {
        int a, b;
        scanf("%d%d", &a, &b);
        G.add(a, b); F.add(b, a);
    }
    rep(i, 1, n) dfs(i);
    rep(i, 1, n) id[i] = i;
    sort(id + 1, id + 1 + n, cmp);
    rep(i, 1, n) printf("%d%c", id[i], " \n"[i == n]);
    rep(i, 1, n) cnt[lim[i]]++;
    rep(i, 1, n) cnt[i] += cnt[i - 1];
    rep(i, 1, n) pos[i] = i - cnt[i];
    rep(i, 1, n) {
        rep(j, 1, n) vis[j] = scnt[j] = 0;
        dfsF(i);
        rep(j, 1, n) if(vis[j]) scnt[lim[j]]++;
        rep(j, 1, n) scnt[j] += scnt[j - 1];
        int ans = lim[i];
        drep(j, lim[i] - 1, 1) {
            if(pos[j - 1] < scnt[n] - scnt[j - 1] - 1) break;
            if(pos[j] < scnt[n] - scnt[j]) break;
            ans = j;
        }
        printf("%d%c", ans, " \n"[i == n]);
    }
    return 0;
}