Luogu1954 [NOI2010] 航空管制

Link

Sol

可以先做一下菜肴制作，再来做这个题就会好很多。

第一问就是菜肴制作，建出反图，原来我们希望1尽可能地在后，在反图上面我们希望拓扑排序的序列字典序越大越好。正的图字典序越小并不一定1就越早出现，所以我们这样处理。那么原来限制k_i现在就变成了n-k_i

第二问就是某一个点进入队列的顺序要发生改变，必须等它前面的点限制都满足完了以后，它进去才是最早的。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2e4 + 5;

int n, m, num;
int head[SIZE], deg[SIZE], lim[SIZE], cpy[SIZE], res[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];
std::priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > q;

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

void addEdge(int u, int v) {
    edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

int sol(int x) {
    while (!q.empty()) q.pop();
    for (int i = 1; i <= n; ++ i) deg[i] = cpy[i];
    for (int i = 1; i <= n; ++ i) {
        if (!deg[i]) q.push(make_pair(n - lim[i], i));
    }
    int cnt = 0;
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (x == u) continue;
        // printf("x:%d cnt:%d lim:%d u:%d\n", x, cnt, lim[u], u);
        if (n - cnt > lim[u]) return n - cnt;
        ++ cnt;
        for (int i = head[u], v; i; i = edge[i].nxt) {
            v = edge[i].to, -- deg[v];
            if (!deg[v]) q.push(make_pair(n - lim[v], v));
        } 
    }
    // puts("");
    return n - cnt;
}

int main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i) lim[i] = read();
    for (int i = 1, u, v; i <= m; ++ i) {
        u = read(), v = read(); std::swap(u, v);
        addEdge(u, v); ++ deg[v];
    }
    for (int i = 1; i <= n; ++ i) cpy[i] = deg[i]; 
    for (int i = 1; i <= n; ++ i) {
        if (!deg[i]) q.push(make_pair(n - lim[i], i));
    }   
    int p = 0;
    while (!q.empty()) {
        int u = q.top().second; q.pop(), res[++ p] = u;
        for (int i = head[u], v; i; i = edge[i].nxt) {
            v = edge[i].to, -- deg[v];
            if (!deg[v]) q.push(make_pair(n - lim[v], v));
        }
    }
    for (int i = n; i; -- i) printf("%d ", res[i]);
    puts("");
    for (int i = 1; i <= n; ++ i) printf("%d ", sol(i));
    puts("");
    return 0;
}