题解 P1954 【[NOI2010]航空管制】

· · 题解

蒟蒻人生中的第一篇题解。

发现大佬们的题解都是用堆来做的贪心，那我就来一篇不用堆，纯 DFS 的题解吧。本题解极其详细，保证各位看官看完即看懂。

1. 朴素思路的产生

考虑题目中的两种条件：

如果只有第一种，那么是一道标准的拓扑排序问题；如果只有第二种条件，那么是一道标准的贪心问题。所以我们很自然地往拓扑排序和贪心相结合的思路上想。

2. 更新航班的 k 值

每个航班都有一个最晚起飞时间，即 k 值。这个值由第二种条件给出。但事实上，这个 k 值还受到第一种条件的约束。显然，若航班 B 依赖于航班 A（即 A→B），则必有 k[A]\leq k[B]-1，所以航班 A 的真实 k 值可由如下表达式求出：k[A] = min(题目中给出的 k[A] , 所有依赖于 A 的航班的 k 值 -1)。

我们通过一次 DFS 即可求解（实际上是一次 DAG 上的动态规划）。

3. 第一问的解

既然所有依赖关系中，后飞的航班 k 值现在一定大于先飞的航班，那么我们很容易想到一种合法安排：根据 k 值从大到小，从后往前安排航班。即先安排 k 值为 n 的航班，再安排 k 值为 n-1 的航班……最后安排 k 值为 1 的航班。

这样做一定是合法的。由于后飞的航班 k 值一定大于先飞的航班，所以所有依赖关系中，后飞的航班一定会安排在先飞的航班之后。故第一种条件一定被满足。

用反证法可证第二种条件一定被满足：若某航班不符合条件二，设其 k 值为 p，被安排的时间为 q，有 p<q。由于 k 值是从后往前排的，则该航班与之前所有航班（共 q 个）的 k 值都 \leq p；即有 q 个航班 k 值 \leq p。所以，我们要在 p 时间内起飞 q 架航班，而 p<q，与一定存在解不符。

实际上，这么做即为按照 k 值从小到大输出所有航班。此即第一问所求的一种可行解。

4. 第二问的解

第一问的做法实际上是从后往前，尽量让每一架航班都尽量晚飞。让航班 A 早飞，即让 A 和 A 的所有祖先（依赖关系中早飞的航班）尽量早飞，这等价于让其他航班尽量晚飞。

我们可以通过对反图进行一次 DFS，标记出 A 和 A 的祖先，然后仿照第一问，在不安排 A 和 A 的祖先的情况下，根据 k 值从大到小，从后往前安排其他航班。

由于其他航班是从后往前安排的，即这些航班占据了可能的、最晚的起飞时间。那么空出来的起飞时间一定是可能情况下最早的。而 A 最早的起飞时间，就是这些空出来的起飞时间中最后一个（其余空出来的时间必须安排 A 的祖先）。我们在从后往前安排其他航班的过程中即可顺便求解。

5. 时间复杂度

由于本做法对于每个节点都求了一次 DFS，故时间复杂度为 O(n(m+n))，不开 O2 耗时 311ms，较为高效。

6. 代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 2005
#define MAXM 10005
int n, m;
int k[MAXN];
struct Edge
{
    int v, nxt;
} e[MAXM << 1];
int head[MAXN], rhead[MAXN], cnt = 1;
// 建图
void add(int u, int v)
{
    e[cnt].v = v;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
    // 顺便存反边，方便后续反图上的DFS
    e[cnt].v = u;
    e[cnt].nxt = rhead[v];
    rhead[v] = cnt++;
}
int vis[MAXN], rvis[MAXN];
int num[MAXN][MAXN], ccnt[MAXN];
// DFS求航班真实k值
int dfs(int cur)
{
    if (vis[cur])
        return k[cur];
    vis[cur] = 1;
    for (int i = head[cur]; i; i = e[i].nxt)
    {
        int res = dfs(e[i].v);
        if (k[cur] > res - 1)
            k[cur] = res - 1;
    }
    // 将航班放到对应k值的航班集合中
    num[k[cur]][ccnt[k[cur]]++] = cur;
    return k[cur];
}
// 反图DFS标记航班及其祖先
void rdfs(int cur)
{
    rvis[cur] = 1;
    for (int i = rhead[cur]; i; i = e[i].nxt)
        if (!rvis[e[i].v])
            rdfs(e[i].v);
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &k[i]);
    while (m--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v);
    }
    // 求所有航班真实k值
    for (int i = 1; i <= n; i++)
        dfs(i);
    // 按照k值从小到大，从前往后输出所有航班
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < ccnt[i]; j++)
            printf("%d ", num[i][j]);
    printf("\n");
    // 求解每个航班的最早起飞时间
    for (int i = 1; i <= n; i++)
    {
        // 反图DFS标记祖先
        memset(rvis, 0, sizeof(rvis));
        rdfs(i);
        // p为当前所考虑的起飞时间
        int p = n;
        // 按照航班k值从大到小，从后往前安排所有其他航班
        for (int j = n; j >= 1; j--)
        {
            // 从后往前遇到的第一个无法安排其他航班的起飞时间
            // 即为空出来的最后一个起飞时间
            // 此即为所求
            if (p > j)
                break;
            for (int t = 0; t < ccnt[j]; t++)
                if (!rvis[num[j][t]])
                    p--;
        }
        // 输出航班i的最早起飞时间
        printf("%d ", p);
    }
    printf("\n");
    return 0;
}