NOI2010 航空管制

题目

bzoj上买一 送一。

算法

知道怎么做之后我对自己很生气，因为这确确实实是一道水题啊！

题目的意思就是说：给出一个有向图，求它的拓扑序列，每个点有限制(l_u)表示(u)这个点在拓扑序列的位置必须比(l_u)前。

这个问题实在不好做，因为求拓扑序列的时候不知道放哪个点会比较好，点与点之间是有影响的。vfk告诉我们，可以把问题反过来，然后就一秒钟变水题了。

问题的反面就是求逆拓扑序，这样的话，(p_u=n - l_u + 1)就表示(u)这个点在逆拓扑序的位置必须比(p_u)后，那当然是越后越好啦，每个点之间就没有影响了。

我们就可以贪心的取点了。

无脑的话，我们可以维护一个优先队列，每次取(p_u)最小的点加入到逆拓扑序中。对于第二个子问题，假设我们要让飞机(u)最早起飞，那就是在逆拓扑序中越后越好，这样我们也可以贪心的一直不把(u)放进序列中，直到实在没办法了才放。
时间复杂度：(O(nm log n))。

优化

我们不一定要让(p_u)最小的点加入拓扑序，假设现在求拓扑序的第(i)位，我们只要随便让一个(p_u geq i)的点进入就行了，所以我们并不需要用优先队列来求第(i)位的点。用点小技巧优化一下就可以做到(O(nm))了。

代码

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2003;
const int MAXM = (int) 1e4 + 3;
 
int n, m;
int limit[MAXN];
pair<int, int> A[MAXN];
 
struct Edge {
    Edge* next;
    int dest;
};
 
Edge memory[MAXM];
Edge* info[MAXN];
Edge* curMem;
 
int que[MAXN];
 
int solve(int X) {
    static int deg[MAXN];
    fill(deg, deg + n + 1, 0);
    for (int i = 1; i <= n; i ++) 
        for (Edge* pt = info[i]; pt; pt = pt->next)
            deg[pt->dest] ++;
 
    int cur = 1;
    int high = 0;
    for (int i = 1; i <= n; i ++) {
        while (cur <= n && A[cur].first <= i) {
            int u = A[cur].second;
            if (u != X && deg[u] == 0) {
                que[++ high] = u;
            }
            cur ++;
        }
        if (high < i) return high;
 
        int u = que[i];
        for (Edge* pt = info[u]; pt; pt = pt->next) {
            int v = pt->dest;
            deg[v] --;
            if (deg[v] == 0 && v != X && limit[v] <= i)
                que[++ high] = v;
        }
    }
    return high;
}
 
int main() {
#ifdef debug
    freopen("input.txt", "r", stdin);
#endif
 
    scanf("%d%d", &n, &m);
 
    for (int i = 1; i <= n; i ++) {
        scanf("%d", limit + i);
        limit[i] = min(limit[i], n);
        limit[i] = n - limit[i] + 1;
        A[i] = make_pair(limit[i], i);
    }
    sort(A + 1, A + 1 + n);
 
    curMem = memory;
    for (int i = 0; i < m; i ++) {
        int a, b;
        scanf("%d%d", &a, &b);
        curMem->dest = a;
        curMem->next = info[b];
        info[b] = curMem ++;
    }
 
    assert(solve(-1) == n);
    for (int i = n; i > 0; i --)
        printf("%d ", que[i]);
    printf("
");
 
    for (int i = 1; i <= n; i ++) {
        printf("%d ", n - solve(i));
    }
    printf("
");
 
    return 0;
}