[NOI2010]航空管制（建反图，拓扑排序，优先队列）

题目链接

洛谷

题意简述

给你一个 DAG，每个点有个值 $k_i$。

第一问：求一个拓扑排序，使每个点出现的位置不超过 $k_i$。

第二问：在满足第一问的拓扑排序中，求每个点分别的最早出现位置。

简要做法

第一眼看到这题，在多少之前 $\rightarrow$ 反过来考虑，因为之前好像做过 PJ 难度的类似题目..

然而第二眼就变成了：拓扑排序裸题！然后愉快地写了个假贪心..

不能随便放过自己的直觉啊..

正解就是建反图，这样一定可以每次选 $k$ 最大的，用优先队列拓扑排序就可以了。

第二问的话，还是建反图，依次考虑每个点，不把当前考虑的点加入优先队列中，直到无法符合要求便是答案。

参考代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> pii;

const int N = 2010;
const int M = 10010;

void add(int u, int v);

int head[N], nxt[M], to[M], cnt;
int n, m, k[N], ind[N], in[N], stk[N], top;
priority_queue<pii> q;

int main()
{
    int i, u, v, x, ans;

    scanf("%d%d", &n, &m);

    for (i = 1; i <= n; ++i) scanf("%d", k + i);

    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d", &u, &v);
        add(v, u);
        ++ind[u];
    }

    memcpy(in, ind, sizeof(in));
    for (i = 1; i <= n; ++i) if (!in[i]) q.push(pii(k[i], i));

    while (!q.empty())
    {
        u = stk[++top] = q.top().second;
        q.pop();
        for (i = head[u]; i; i = nxt[i])
        {
            v = to[i];
            if (--in[v] == 0) q.push(pii(k[v], v));
        }
    }

    while (top) printf("%d ",stk[top--]);
    puts("");

    for (x = 1; x <= n; ++x)
    {
        ans = n;
        memcpy(in, ind, sizeof(in));
        for (i = 1; i <= n; ++i) if (!in[i]) q.push(pii(k[i], i));

        while (!q.empty())
        {
            u = q.top().second;
            q.pop();
            if (u == x) continue;
            if (k[u] < ans)
            {
                while (!q.empty()) q.pop();
                break;
            }
            --ans;
            for (i = head[u]; i; i = nxt[i])
            {
                v = to[i];
                if (--in[v] == 0) q.push(pii(k[v], v));
            }
        }

        printf("%d ", ans);
    }

    return 0;
}

void add(int u, int v)
{
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}