拓扑排序学习笔记（【题解】P1113 杂物）

Keith_2006 · 2020-02-24 20:59:10 · 题解

这是一道拓扑排序的模板题

0 写在前面

UPD 2024-09-08 看自己四年前的博客重新学习拓扑排序，顺便修改笔误。

UPD 2020-05-13 修改了代码中没有初始化的小错误，修改了格式。

关于题解：虽然这道题的题解数量比较多，但是我认为我的题解相对来说比较清晰，易于理解，希望修改后管理能够通过审核。

此题解主要介绍拓扑排序的实现方法（如果有不对的地方还请大佬指教），文章略长，但是我认为还是比较清晰的，希望各位能够认真看完。

在学习之前，请确保你拥有以下前置知识：

图论相关的基本概念
建图、存图
图的遍历
非常入门的 DP

下面进入正文

1 引入

拓扑排序是一类用于处理 DAG（Directed acyclic graph），即有向无环图上的问题。

以这道题为例，我们分析拓扑排序的作用：

显然地，本题中各项工作是有一定的依赖条件的，也就是说我们在进行工作 X 之前可能需要先进行一些其他的工作。

而完成工作 X 所需的时间和所有 X 所依赖的工作完成的时间的最大值有关。（应该还好理解吧）

在这道题中，我们可以列出一个简单的 DP 转移方程：

f_i=\max\{pre_i\}+a_i

其中 f_i 为从最开始到进行完第 i 项任务所需的时间，pre_i 为 i 号结点的前驱数组，a_i 为做第 i 件事所需的时间。

但是，我们如果直接进行 dfs 遍历，可能会出现一个问题：在我们计算 f_i 的时候，还存在没有计算过的 pre_i，从而导致结果计算错误。

那么，我们在计算的时候，应该确保在计算一个结点 u 时，所有与连向它的点都已经被计算过。

而实现这一过程就利用到了今天的主角：拓扑排序（topo sort）

2 拓扑排序记忆化搜索！

蛤？你不是要说拓扑排序吗？

别急，我们先来看一下记忆化搜索的方法。通过此方法，我们仍然可以达到拓扑排序的目的。

先放上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>

#define ll long long

using namespace std;

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}

//以上都是模板，不解释

const int N=10005;

int a[N],f[N];  //f数组含义如上所示
vector <int> edge[N];  //我习惯使用vector邻接表存图，其他存图方式做法类似

//这里开始是重点

int dfs(int x) {
    if (f[x]) return f[x];  //假如已经被访问过，直接返回
    for (int i=0;i<edge[x].size();i++) {  //循环：x 的每条出边指向的点
        f[x]=max(f[x],dfs(edge[x][i]));  //DP，求pre的最大值
    }
    f[x]+=a[x];  //加上a[i]的值，即DP方程
    return f[x];  //返回DP的结果
}

int main() {
    int n=read();
    for (int i=1;i<=n;i++) {
        int x=read(); //编号
        a[i]=read();  //所需时间
        int y=read();
        //以下的读入不解释
        while (y!=0) {
            edge[y].push_back(x);
            y=read();
        }
    }
    //对于每一个点进行dfs，求f的值
    int ans=0;
    for (int i=1;i<=n;i++) {
        ans=max(ans,dfs(i));  //取最大值
    }
    printf("%d\n",ans);  //输出结果
    return 0;
}

那么，为什么这个代码可以实现拓扑排序的目的呢？

先看一张图：

在主函数的 for 循环中执行 dfs(1) 的时候，2 号点的前驱 3 号点还没有被访问。但是在执行dfs(3)的时候，2 号点就被访问了。

同理，4号点亦是如此，读者可自己在头脑中推演一遍。

也就是说，在整个循环中，一定会存在一次dfs(i)的时候，其前驱全部被访问。

因此就实现了拓扑排序的功能。

其实，这个代码可以认为是广义上的拓扑排序，即实现了对结点访问顺序进行排序的功能，只是实现的方式为 dfs 而已。

3 “真正”的拓扑排序（也许可以说是 bfs 式拓扑排序）

这种拓扑排序通常是指狭义上的拓扑排序，当然，我更喜欢将整个过程理解为一个bfs的过程。

对于一个bfs的过程而言，我们首先要找到搜索的起始点，也就是一开始加入队列中的点。

显然，这个点不能有任何前驱，因此我们要找入度为0的结点加入队列。

有读者可能要问了：要是没有入度为 0 的结点该怎么办呢？

其实，这种情况在一个 DAG 中是不存在的。下面证明：一个 DAG 中一定存在至少一个入度为 0 的结点。

利用反证法，假设不存在任何一个入度为 0 的结点，则每个结点的入度至少为1。

这样，对于结点 G_1，一定存在 G_2 为 G_1 的前驱。同理，一定存在 G_3 为 G_2 的前驱。以此类推，假设图共有 n 个结点，那么一定有 G_n 为 G_{n-1} 的前驱。

那么，如果 G_{n} 存在前驱 G_i 满足 1 \leq i \leq n，那么就会形成一个环，与条件 DAG 矛盾。如果该店不存在前驱，则那个点的入度为0，与假设矛盾。

故此，我们证明了不存在 DAG 中没有入度为 0 的结点的情况。

然后，我们遍历每个结点 x 的出边，考虑到达的一个点，假设为 y，我们删去 x 到 y 的边。

在代码实现中，其实是取出队列的队头 x，将 y 的入度减一即可。在此过程中，通常利用动态规划对数据进行维护。在这道题目中，便是这一行代码f[y]=max(f[y],f[x]+a[y]);

当一个点的入度减到 0 时，说明所有它的所有前驱已经被计算过了，那么我们将它插入队列。

重复以上步骤，直到队列为空。这时我们就已经统计出了答案。

总结一下，此种拓扑排序共有四个主要步骤：

初始化队列，将入度为 0 的节点放入队列。
取出队首，遍历其出边，将能够到达的点入度减一，同时维护答案数组。
若在此时一个点的入度变为 0，那么将其加入队列。
回到第二步，直到队列为空。

代码放出来给读者参考：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>

#define ll long long

using namespace std;

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}

const int N=500005;

int ind[N],f[N],a[N];  //ind--入度   f--答案   a--时间
vector <int> edge[N];
queue <int> q;

int main() {
    int n=read();
    for (int i=1;i<=n;i++) {
        int x=read();
        a[i]=read();
        while (int y=read()) {
            if (!y) break;
            edge[y].push_back(x);
            ind[x]++;
        }
    }
    //步骤一
    for (int i=1;i<=n;i++) {
        if (ind[i]==0) {
            q.push(i);
            f[i]=a[i];
        }
    };
    while (!q.empty()) {
        int rhs=q.front();
        q.pop();
        //步骤二
        for (int i=0;i<edge[rhs].size();i++) {
            int u=edge[rhs][i];
            ind[u]--;
            if (ind[u]==0) q.push(u);  //步骤三
            f[u]=max(f[u],f[rhs]+a[u]);
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++) {
        ans=max(ans,f[i]);   //统计答案
    }
    printf("%d\n",ans);
    return 0;
}

考虑到上面我已经讲地比较清楚了，这里代码不加过多注释，仅标记关键处。

4 一些题目

做完这一道拓扑排序模板题之后，大家可以移步：

P4017 最大食物链计数

P1983 车站分级

很多 DAG 上的 DP 都需要依赖于拓扑排序，也有很多题目是需要先进行缩点然后再拓扑排序，比如说这个题：

P3387 【模板】缩点

（其实很大一部分和强连通分量有关的题目都利用到拓扑排序）

完结撒花 QAQ！

如果觉得文章有一些帮助的话不妨点个赞哦！谢谢！

拓扑排序学习笔记 （【题解】P1113 杂物）