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

## 这是一道拓扑排序的模板题 ### 0 写在前面 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 ~~拓扑排序~~ 记忆化搜索！ 蛤？你不是要说拓扑排序吗？ 别急，我们先来看一下记忆化搜索的方法。通过此方法，我们仍然可以达到拓扑排序的目的。 先放上代码: ```cpp #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-1}$ 存在前驱 $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时**，说明所有它的**所有前驱已经被计算过了**，那么我们将它**插入队列**。 **重复以上步骤，直到队列为空**。这时我们就已经统计出了答案。 #### 总结一下，此种拓扑排序共有四个主要步骤： 1. **初始化队列，将入度为 $0$ 的节点放入队列。** 2. **取出队首，遍历其出边，将能够到达的点入度减一，同时维护答案数组。** 3. **若在此时一个点的入度变为 $1$，那么将其加入队列。** 4. **回到第二步，直到队列为空。** 代码放出来给读者参考： ```cpp #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 最大食物链计数](https://www.luogu.com.cn/problem/P4017) [P1983 车站分级](https://www.luogu.com.cn/problem/P1983) 很多 DAG 上的 DP 都需要依赖于拓扑排序，也有很多题目是需要先进行缩点然后再拓扑排序，比如说这个题： [P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387) （其实很大一部分和强连通分量有关的题目都利用到拓扑排序） *** #### 完结撒花 QAQ！ *如果觉得文章有一些帮助的话不妨点个赞哦！谢谢！*