自动搬运

查看原文

来自洛谷，原作者为

	SBofGaySchool SB of gay school BU PA anything!

搬运于2025-08-24 21:32:16，当前版本为作者最后更新于2020-08-12 23:59:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

发现大佬们的题解都是用堆来做的贪心，那我就来一篇不用堆，纯 $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;
}