图论

2020-02-27 205浏览

  • 1.图论基础 图论算法 例题 图论及其应用 hzwer,miskcoo 北京大学, 清华大学 2016 年 8 月 18 日 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 1 / 75
  • 2.图论基础 图论算法 例题 图论及其应用 hzwer,miskcoo 北京大学, 清华大学 2016 年 8 月 18 日 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 2 / 75
  • 3.图论基础 图论算法 1 图论基础 图的存储 一些概念 2 图论算法 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 3 / 75
  • 4.图论基础 图的存储 图论算法 1 图论基础 图的存储 一些概念 2 图论算法 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 4 / 75
  • 5.图论基础 图论算法 例题 图的存储 图的矩阵存储 图可以直接用二维数组来存储。具体来说，如果一张图有 n 个结点，那 么就使用 n × n 的二维数组来存储。 数组的每个元素的值代表了对应的边的数量。例如上面这张图就可以存 储如下：   0101 00 0 0 1 0 11 0000 这种方式通常用来存储十分稠密的图，可以比较快地定位到某一条边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 5 / 75
  • 6.图论基础 图论算法 例题 图的存储 图的链表存储 图还可以用邻接表来存储。也就是每个结点维护一个链表，这个链表存 储着以当前结点为开头的边。 通常情况下我们都是用这种方法来存储图的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 6 / 75
  • 7.图论基础 一些概念 图论算法 1 图论基础 图的存储 一些概念 2 图论算法 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 7 / 75
  • 8.图论基础 图论算法 例题 一些概念 一些概念 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 8 / 75
  • 9.图论基础 图论算法 例题 一些概念 一些概念 • 顶点的度：在无向图中，某个顶点的度是与它相关联的边的数目。在 有向图中，一个顶点的出度是以它为起始的边的数目，入度是以它为 终止的边的数目。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 8 / 75
  • 10.图论基础 图论算法 例题 一些概念 一些概念 • 顶点的度：在无向图中，某个顶点的度是与它相关联的边的数目。在 有向图中，一个顶点的出度是以它为起始的边的数目，入度是以它为 终止的边的数目。 • 简单路径：顶点不重复的路径。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 8 / 75
  • 11.图论基础 图论算法 例题 一些概念 一些概念 • 顶点的度：在无向图中，某个顶点的度是与它相关联的边的数目。在 有向图中，一个顶点的出度是以它为起始的边的数目，入度是以它为 终止的边的数目。 • 简单路径：顶点不重复的路径。 • 自环：从某个顶点出发连向它自身的边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 8 / 75
  • 12.图论基础 图论算法 例题 一些概念 一些概念 • 顶点的度：在无向图中，某个顶点的度是与它相关联的边的数目。在 有向图中，一个顶点的出度是以它为起始的边的数目，入度是以它为 终止的边的数目。 • 简单路径：顶点不重复的路径。 • 自环：从某个顶点出发连向它自身的边。 • 环：从某个顶点出发再回到自身的路径，又称回路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 8 / 75
  • 13.图论基础 图论算法 例题 一些概念 一些概念 • 顶点的度：在无向图中，某个顶点的度是与它相关联的边的数目。在 有向图中，一个顶点的出度是以它为起始的边的数目，入度是以它为 终止的边的数目。 • 简单路径：顶点不重复的路径。 • 自环：从某个顶点出发连向它自身的边。 • 环：从某个顶点出发再回到自身的路径，又称回路。 • 重边：从一个顶点到另一个顶点有两条边直接相连。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 8 / 75
  • 14.图论基础 图论算法 例题 一些概念 一些概念 在无向图中，若从顶点 u 到 v 存在路径，那么称顶点 u 和 v 是连通的。 如果无向图中任意一对顶点都是连通的，那么称此图为连通图。如果一个无 向图不是连通的，则称它的一个极大连通子图为连通分量。这里的极大是指 顶点个数极大。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 9 / 75
  • 15.图论基础 图论算法 例题 一些概念 一些概念 在无向图中，若从顶点 u 到 v 存在路径，那么称顶点 u 和 v 是连通的。 如果无向图中任意一对顶点都是连通的，那么称此图为连通图。如果一个无 向图不是连通的，则称它的一个极大连通子图为连通分量。这里的极大是指 顶点个数极大。 在有向图中，如果每一对顶点 u 和 v，既存在从 u 到 v 的路径，又存 在从 v 到 u 的路径，那么称此图为强连通图。对于非强连通图，其极大强 连通子图成为其强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 9 / 75
  • 16.图论基础 图论算法 例题 一些概念 一些概念 在无向图中，若从顶点 u 到 v 存在路径，那么称顶点 u 和 v 是连通的。 如果无向图中任意一对顶点都是连通的，那么称此图为连通图。如果一个无 向图不是连通的，则称它的一个极大连通子图为连通分量。这里的极大是指 顶点个数极大。 在有向图中，如果每一对顶点 u 和 v，既存在从 u 到 v 的路径，又存 在从 v 到 u 的路径，那么称此图为强连通图。对于非强连通图，其极大强 连通子图成为其强连通分量。 在有向图中，若不考虑边的方向时图才为连通图，那么称原有向图为弱 连通。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 9 / 75
  • 17.图论基础 图论算法 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 10 / 75
  • 18.图论基础 拓扑排序 图论算法 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 11 / 75
  • 19.图论基础 图论算法 例题 拓扑排序 拓扑排序 现在来考虑一个问题：现在有一个工程，这个工程被分成了很多部分。 有一些部分要求前面某些部分完成后才可以开始进行。有些部分则可以同时 进行。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 12 / 75
  • 20.图论基础 图论算法 例题 拓扑排序 拓扑排序 现在来考虑一个问题：现在有一个工程，这个工程被分成了很多部分。 有一些部分要求前面某些部分完成后才可以开始进行。有些部分则可以同时 进行。 我们可以把每个部分看作一个结点，刚刚这些限制看成是有向边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 12 / 75
  • 21.图论基础 图论算法 例题 拓扑排序 拓扑排序 现在来考虑一个问题：现在有一个工程，这个工程被分成了很多部分。 有一些部分要求前面某些部分完成后才可以开始进行。有些部分则可以同时 进行。 我们可以把每个部分看作一个结点，刚刚这些限制看成是有向边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 12 / 75
  • 22.图论基础 图论算法 例题 拓扑排序 拓扑排序 现在来考虑一个问题：现在有一个工程，这个工程被分成了很多部分。 有一些部分要求前面某些部分完成后才可以开始进行。有些部分则可以同时 进行。 我们可以把每个部分看作一个结点，刚刚这些限制看成是有向边。 比如说这张图就可以看成是这样一个限制。这样的图有个特点：没有 环！ 因此这样的图也被成为 Directed Acyclic Graph（有向无环图）。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 12 / 75
  • 23.图论基础 图论算法 例题 拓扑排序 拓扑排序 求出一个这个工程的工作序列的算法被成为拓扑排序。 比如说 1，5，2，3，6，4 就可以算作一个工作序列。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 13 / 75
  • 24.图论基础 图论算法 例题 拓扑排序 拓扑排序 求出一个这个工程的工作序列的算法被成为拓扑排序。 比如说 1，5，2，3，6，4 就可以算作一个工作序列。 拓扑排序的过程大概是这样的： hzwer,miskcoo 图论及其应用 北京大学, 清华大学 13 / 75
  • 25.图论基础 图论算法 例题 拓扑排序 拓扑排序 求出一个这个工程的工作序列的算法被成为拓扑排序。 比如说 1，5，2，3，6，4 就可以算作一个工作序列。 拓扑排序的过程大概是这样的： 1 选择一个入度为 0 的结点并直接输出。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 13 / 75
  • 26.图论基础 图论算法 例题 拓扑排序 拓扑排序 求出一个这个工程的工作序列的算法被成为拓扑排序。 比如说 1，5，2，3，6，4 就可以算作一个工作序列。 拓扑排序的过程大概是这样的： 1 选择一个入度为 0 的结点并直接输出。 2 删除这个结点以及与它关联的所有边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 13 / 75
  • 27.图论基础 图论算法 例题 拓扑排序 拓扑排序 求出一个这个工程的工作序列的算法被成为拓扑排序。 比如说 1，5，2，3，6，4 就可以算作一个工作序列。 拓扑排序的过程大概是这样的： 1 选择一个入度为 0 的结点并直接输出。 2 删除这个结点以及与它关联的所有边。 3 重复步骤 (1) 和 (2)，直到找不到入度为 0 的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 13 / 75
  • 28.图论基础 图论算法 例题 拓扑排序 拓扑排序 求出一个这个工程的工作序列的算法被成为拓扑排序。 比如说 1，5，2，3，6，4 就可以算作一个工作序列。 拓扑排序的过程大概是这样的： 1 选择一个入度为 0 的结点并直接输出。 2 删除这个结点以及与它关联的所有边。 3 重复步骤 (1) 和 (2)，直到找不到入度为 0 的结点。 通常情况下，在实现的时候会维护一个队列以及每个结点的入度。在删 除边的时候顺便把相应结点的入度减去，当这个结点入度为 0 的时候直接 将其加入队列。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 13 / 75
  • 29.图论基础 图论算法 例题 拓扑排序 例题 1 小明要去一个国家旅游。这个国家有 n 个城市，编号为 1 n，并且有 m 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市 i 停止。 所以他就需要选择最先到达的城市，并制定一条路线以城市 i 为终点， 使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足 这个前提下还希望游览的城市尽量多。 现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不 知道所有城市具体的位置。现在对于所有的 i，都需要你为小明制定一条路 线，并求出以城市 i 为终点最多能够游览多少个城市。 其中 1 ≤ n ≤ 100000, 1 ≤ m ≤ 200000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 14 / 75
  • 30.图论基础 图论算法 拓扑排序 例题 1 最长路 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 15 / 75
  • 31.图论基础 图论算法 拓扑排序 例题 1 最长路 DAG hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 15 / 75
  • 32.图论基础 图论算法 拓扑排序 例题 1 最长路 DAG 拓扑排序的过程中直接 DP hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 15 / 75
  • 33.图论基础 图论算法 例题 拓扑排序 例题 2 CF698B 给出 n 个结点的父亲，问至少修改多少个结点的父亲，能使整张图变成 一棵树（根的父亲为自己），要求输出任一方案。 其中 1 ≤ n ≤ 200000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 16 / 75
  • 34.图论基础 图论算法 拓扑排序 例题 2 CF698B 思考环和链的答案 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 17 / 75
  • 35.图论基础 图论算法 例题 拓扑排序 例题 2 CF698B 思考环和链的答案 图的各个弱连通块是环 + 内向树，或者树/环。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 17 / 75
  • 36.图论基础 图论算法 例题 拓扑排序 例题 2 CF698B 思考环和链的答案 图的各个弱连通块是环 + 内向树，或者树/环。 先用拓扑排序把内向树消掉 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 17 / 75
  • 37.图论基础 图论算法 例题 拓扑排序 例题 2 CF698B 思考环和链的答案 图的各个弱连通块是环 + 内向树，或者树/环。 先用拓扑排序把内向树消掉 剩下来的是一些环，每个环随便选一个结点当根，然后再把所有的根连 在一起。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 17 / 75
  • 38.图论基础 图论算法 例题 拓扑排序 例题 2 CF698B 思考环和链的答案 图的各个弱连通块是环 + 内向树，或者树/环。 先用拓扑排序把内向树消掉 剩下来的是一些环，每个环随便选一个结点当根，然后再把所有的根连 在一起。 答案是环数-（是否存在自环） hzwer,miskcoo 图论及其应用 北京大学, 清华大学 17 / 75
  • 39.图论基础 生成树 图论算法 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 18 / 75
  • 40.图论基础 图论算法 例题 生成树 最小生成树 生成树：无向连通图 G 的一个子图如果是包含 G 的所有顶点的树，那 么就称这个子图为 G 的生成树。 我们称生成树各边权值和为该树的权。对于无向连通图来说，权最小的 生成树被成为最小生成树。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 19 / 75
  • 41.图论基础 图论算法 例题 生成树 最小生成树 生成树：无向连通图 G 的一个子图如果是包含 G 的所有顶点的树，那 么就称这个子图为 G 的生成树。 我们称生成树各边权值和为该树的权。对于无向连通图来说，权最小的 生成树被成为最小生成树。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 19 / 75
  • 42.图论基础 图论算法 例题 生成树 Kruskal 算法 Kruskal 算法是能够在 O(m log m) 的时间内得到一个最小生成树的算 法。它主要是基于贪心的思想： hzwer,miskcoo 图论及其应用 北京大学, 清华大学 20 / 75
  • 43.图论基础 图论算法 例题 生成树 Kruskal 算法 Kruskal 算法是能够在 O(m log m) 的时间内得到一个最小生成树的算 法。它主要是基于贪心的思想： 1 将边按照边权从小到大排序，并建立一个没有边的图 T。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 20 / 75
  • 44.图论基础 图论算法 例题 生成树 Kruskal 算法 Kruskal 算法是能够在 O(m log m) 的时间内得到一个最小生成树的算 法。它主要是基于贪心的思想： 1 将边按照边权从小到大排序，并建立一个没有边的图 T。 2 选出一条没有被选过的边权最小的边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 20 / 75
  • 45.图论基础 图论算法 例题 生成树 Kruskal 算法 Kruskal 算法是能够在 O(m log m) 的时间内得到一个最小生成树的算 法。它主要是基于贪心的思想： 1 将边按照边权从小到大排序，并建立一个没有边的图 T。 2 选出一条没有被选过的边权最小的边。 3 如果这条边两个顶点在 T 中所在的连通块不相同，那么将它加入图 T。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 20 / 75
  • 46.图论基础 图论算法 例题 生成树 Kruskal 算法 Kruskal 算法是能够在 O(m log m) 的时间内得到一个最小生成树的算 法。它主要是基于贪心的思想： 1 将边按照边权从小到大排序，并建立一个没有边的图 T。 2 选出一条没有被选过的边权最小的边。 3 如果这条边两个顶点在 T 中所在的连通块不相同，那么将它加入图 T。 4 重复 (2) 和 (3) 直到图 T 连通为止。 由于只需要维护连通性，可以不需要真正建立图 T，可以用并查集来维 护。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 20 / 75
  • 47.图论基础 图论算法 例题 生成树 Kruskal 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 21 / 75
  • 48.图论基础 图论算法 例题 生成树 Kruskal 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 21 / 75
  • 49.图论基础 图论算法 例题 生成树 Kruskal 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 21 / 75
  • 50.图论基础 图论算法 例题 生成树 Kruskal 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 21 / 75
  • 51.图论基础 图论算法 例题 生成树 Kruskal 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 21 / 75
  • 52.图论基础 图论算法 例题 生成树 Kruskal 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 21 / 75
  • 53.图论基础 图论算法 例题 生成树 Prim 算法 Prim 算法和 Kruskal 算法一样也是寻找最小生成树的一种方法。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 22 / 75
  • 54.图论基础 图论算法 例题 生成树 Prim 算法 Prim 算法和 Kruskal 算法一样也是寻找最小生成树的一种方法。 1 先建立一个只有一个结点的树，这个结点可以是原图中任意的一个结 点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 22 / 75
  • 55.图论基础 图论算法 例题 生成树 Prim 算法 Prim 算法和 Kruskal 算法一样也是寻找最小生成树的一种方法。 1 先建立一个只有一个结点的树，这个结点可以是原图中任意的一个结 点。 2 使用一条边扩展这个树，要求这条边一个顶点在树中另一个顶点不在 树中，并且这条边的权值要求最小。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 22 / 75
  • 56.图论基础 图论算法 例题 生成树 Prim 算法 Prim 算法和 Kruskal 算法一样也是寻找最小生成树的一种方法。 1 先建立一个只有一个结点的树，这个结点可以是原图中任意的一个结 点。 2 使用一条边扩展这个树，要求这条边一个顶点在树中另一个顶点不在 树中，并且这条边的权值要求最小。 3 重复步骤 (2) 直到所有顶点都在树中。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 22 / 75
  • 57.图论基础 图论算法 例题 生成树 Prim 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 23 / 75
  • 58.图论基础 图论算法 例题 生成树 Prim 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 24 / 75
  • 59.图论基础 图论算法 例题 生成树 Prim 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 25 / 75
  • 60.图论基础 图论算法 例题 生成树 Prim 算法 具体实现的时候，可以为每个结点维护一个 key 值，表示它到已经选中 的顶点中权值最小的边的权值。每次就在所有没有选中的顶点中找到 key 值最小的顶点，以及与它相关联的那条边加入树中并且更新与这个顶点相关 联的所有顶点的 key 值。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 25 / 75
  • 61.图论基础 图论算法 例题 生成树 Prim 算法 具体实现的时候，可以为每个结点维护一个 key 值，表示它到已经选中 的顶点中权值最小的边的权值。每次就在所有没有选中的顶点中找到 key 值最小的顶点，以及与它相关联的那条边加入树中并且更新与这个顶点相关 联的所有顶点的 key 值。 这是可以用堆维护的，它的复杂度是 O(m log n)。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 25 / 75
  • 62.图论基础 图论算法 最近公共祖先和倍增算法 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 26 / 75
  • 63.图论基础 图论算法 例题 最近公共祖先和倍增算法 最近公共祖先 在一棵树上，两个结点的最近公共祖先（LCA） 是它们的公共祖先中深度最大的那个顶点。 比如说，在左边的树中，顶点 x 和 y 的公共祖先 用绿色标出，其中深绿色的顶点就是它们的最近公共 祖先。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 27 / 75
  • 64.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 常见的求最近公共祖先的算法是倍增算法。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 28 / 75
  • 65.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 常见的求最近公共祖先的算法是倍增算法。 首先对于每个结点先进行 DFS 预处理出它的深度，再记录下它们往父 亲方向走 20, 21, 22, · · · , 2k 步所到达的结点。在这里 2k 大于整棵树的最 大深度。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 28 / 75
  • 66.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 常见的求最近公共祖先的算法是倍增算法。 首先对于每个结点先进行 DFS 预处理出它的深度，再记录下它们往父 亲方向走 20, 21, 22, · · · , 2k 步所到达的结点。在这里 2k 大于整棵树的最 大深度。 预处理完后，需要查询两个点 u 和 v 的 LCA 的时候，先将 u 和 v 中深 度较大的一个利用先前处理出的数组走到和另一个结点相同的深度，这的所 需要的操作次数不会超过 log2 depth(u) − depth(v) 。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 28 / 75
  • 67.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 常见的求最近公共祖先的算法是倍增算法。 首先对于每个结点先进行 DFS 预处理出它的深度，再记录下它们往父 亲方向走 20, 21, 22, · · · , 2k 步所到达的结点。在这里 2k 大于整棵树的最 大深度。 预处理完后，需要查询两个点 u 和 v 的 LCA 的时候，先将 u 和 v 中深 度较大的一个利用先前处理出的数组走到和另一个结点相同的深度，这的所 需要的操作次数不会超过 log2 depth(u) − depth(v) 。 接下来从 k 开始往下枚举，如果 u 和 v 如果往上走 2i 后不相同，那么 就将它们一起往上走这么多步。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 28 / 75
  • 68.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 常见的求最近公共祖先的算法是倍增算法。 首先对于每个结点先进行 DFS 预处理出它的深度，再记录下它们往父 亲方向走 20, 21, 22, · · · , 2k 步所到达的结点。在这里 2k 大于整棵树的最 大深度。 预处理完后，需要查询两个点 u 和 v 的 LCA 的时候，先将 u 和 v 中深 度较大的一个利用先前处理出的数组走到和另一个结点相同的深度，这的所 需要的操作次数不会超过 log2 depth(u) − depth(v) 。 接下来从 k 开始往下枚举，如果 u 和 v 如果往上走 2i 后不相同，那么 就将它们一起往上走这么多步。 结束后如果 u 和 v 仍然不相等，再往上走一步。最后的顶点就是它们的 LCA。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 28 / 75
  • 69.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 29 / 75
  • 70.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 倍增算法预处理的复杂度预处理是 O(n log n)，每次查询都是 O(log n)。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 30 / 75
  • 71.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 倍增算法预处理的复杂度预处理是 O(n log n)，每次查询都是 O(log n)。 不仅如此，我们可以动态地给树增加一些叶子结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 30 / 75
  • 72.图论基础 图论算法 例题 最近公共祖先和倍增算法 倍增算法 倍增算法预处理的复杂度预处理是 O(n log n)，每次查询都是 O(log n)。 不仅如此，我们可以动态地给树增加一些叶子结点。 此外，在预处理的时候还可以顺便记录下这段路径的权值最大值，最小 值或者权值和之类的信息，这样就可以在 O(log n) 的时间内求出树上两点 间路径权值的最大值、最小值还有权值和。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 30 / 75
  • 73.图论基础 图论算法 例题 最近公共祖先和倍增算法 NOIP2013. 货车运输 A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条 道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，每辆货 车需要从一个城市运输到另一个城市。司机们想知道每辆车在不超过车辆限 重的情况下，最多能运多重的货物。 其中 0 < n < 104, 0 < m < 5 × 104, 0 < q < 3 × 104 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 31 / 75
  • 74.图论基础 图论算法 例题 最近公共祖先和倍增算法 NOIP2013. 货车运输 A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条 道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，每辆货 车需要从一个城市运输到另一个城市。司机们想知道每辆车在不超过车辆限 重的情况下，最多能运多重的货物。 其中 0 < n < 104, 0 < m < 5 × 104, 0 < q < 3 × 104 最大生成树 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 31 / 75
  • 75.图论基础 图论算法 例题 最近公共祖先和倍增算法 NOIP2013. 货车运输 A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条 道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，每辆货 车需要从一个城市运输到另一个城市。司机们想知道每辆车在不超过车辆限 重的情况下，最多能运多重的货物。 其中 0 < n < 104, 0 < m < 5 × 104, 0 < q < 3 × 104 最大生成树、倍增算路径最小值 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 31 / 75
  • 76.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 1 给出一个有 n 个结点，m 条边的无向图，判断其最小生成树是否唯一。 其中 0 < n < 104, 0 < m < 106。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 32 / 75
  • 77.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 1 给出一个有 n 个结点，m 条边的无向图，判断其最小生成树是否唯一。 其中 0 < n < 104, 0 < m < 106。 MST 什么时候唯一？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 32 / 75
  • 78.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 1 给出一个有 n 个结点，m 条边的无向图，判断其最小生成树是否唯一。 其中 0 < n < 104, 0 < m < 106。 MST 什么时候唯一？ 加入一条非树边会形成环 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 32 / 75
  • 79.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 1 给出一个有 n 个结点，m 条边的无向图，判断其最小生成树是否唯一。 其中 0 < n < 104, 0 < m < 106。 MST 什么时候唯一？ 加入一条非树边会形成环 找到环上除了新加入的边外权值最大的边, 该边权值小于这条非树边 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 32 / 75
  • 80.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 2 BZOJ1977 给出一个有 n 个结点，m 条边的无向图，求其严格次小生成树。 其中 0 < n < 105, 0 < m < 3 ∗ 105。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 33 / 75
  • 81.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 2 BZOJ1977 给出一个有 n 个结点，m 条边的无向图，求其严格次小生成树。 其中 0 < n < 105, 0 < m < 3 ∗ 105。 最小生成树和严格次小的区别？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 33 / 75
  • 82.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 2 BZOJ1977 给出一个有 n 个结点，m 条边的无向图，求其严格次小生成树。 其中 0 < n < 105, 0 < m < 3 ∗ 105。 最小生成树和严格次小的区别？ 用非树边替换最小生成树的一条边 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 33 / 75
  • 83.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 2 BZOJ1977 给出一个有 n 个结点，m 条边的无向图，求其严格次小生成树。 其中 0 < n < 105, 0 < m < 3 ∗ 105。 最小生成树和严格次小的区别？ 用非树边替换最小生成树的一条边 枚举每一条非树边找俩顶点树链上的最大边（如果最大边相同与非树边 边权相同则找次大边）然后更新最小增量 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 33 / 75
  • 84.图论基础 图论算法 例题 最近公共祖先和倍增算法 例题 2 BZOJ1977 给出一个有 n 个结点，m 条边的无向图，求其严格次小生成树。 其中 0 < n < 105, 0 < m < 3 ∗ 105。 最小生成树和严格次小的区别？ 用非树边替换最小生成树的一条边 枚举每一条非树边找俩顶点树链上的最大边（如果最大边相同与非树边 边权相同则找次大边）然后更新最小增量 最大边和次大边可以通过树上倍增求出 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 33 / 75
  • 85.图论基础 单源最短路 图论算法 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 34 / 75
  • 86.图论基础 图论算法 例题 单源最短路 Bellman-Ford 算法 给定了一个边带有权值（可以为负数）的有向图（不包含负环）和一个 指定的顶点 s。要求求出从 s 到其余各点的最短路径长度。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 35 / 75
  • 87.图论基础 图论算法 例题 单源最短路 Bellman-Ford 算法 给定了一个边带有权值（可以为负数）的有向图（不包含负环）和一个 指定的顶点 s。要求求出从 s 到其余各点的最短路径长度。 Bellman-Ford 算法是一个比较直观的求解单源最段路问题的算法。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 35 / 75
  • 88.图论基础 图论算法 例题 单源最短路 Bellman-Ford 算法 给定了一个边带有权值（可以为负数）的有向图（不包含负环）和一个 指定的顶点 s。要求求出从 s 到其余各点的最短路径长度。 Bellman-Ford 算法是一个比较直观的求解单源最段路问题的算法。 我们可以肯定最短路径包含的边的条数不会超过 n-1 个，如果超过这个 数，那么肯定形成了一个环，又因为这个环权值是正的，我们可以将路径上 这个环删除，路径长度就会变小。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 35 / 75
  • 89.图论基础 图论算法 例题 单源最短路 Bellman-Ford 算法 这个算法主要是构造一个最短路径长度数组的序列：dist[1][u], dist[2][u], · · · , dist[n − 1][u]。 其中 dist[k][u] 表示从源 s 到 u 至多经过 k 条边的最短路径的长度。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 36 / 75
  • 90.图论基础 图论算法 例题 单源最短路 Bellman-Ford 算法 这个算法主要是构造一个最短路径长度数组的序列：dist[1][u], dist[2][u], · · · , dist[n − 1][u]。 其中 dist[k][u] 表示从源 s 到 u 至多经过 k 条边的最短路径的长度。 显然我们可以得到这样的关系： hzwer,miskcoo 图论及其应用 北京大学, 清华大学 36 / 75
  • 91.图论基础 图论算法 例题 单源最短路 Bellman-Ford 算法 这个算法主要是构造一个最短路径长度数组的序列：dist[1][u], dist[2][u], · · · , dist[n − 1][u]。 其中 dist[k][u] 表示从源 s 到 u 至多经过 k 条边的最短路径的长度。 显然我们可以得到这样的关系： dist[1][u] = w[s][u] hzwer,miskcoo 图论及其应用 北京大学, 清华大学 36 / 75
  • 92.图论基础 图论算法 例题 单源最短路 Bellman-Ford 算法 这个算法主要是构造一个最短路径长度数组的序列：dist[1][u], dist[2][u], · · · , dist[n − 1][u]。 其中 dist[k][u] 表示从源 s 到 u 至多经过 k 条边的最短路径的长度。 显然我们可以得到这样的关系： dist[1][u] = w[s][u] dist[k][u] = min(dist[k − 1][u], min (dist[k − 1][v] + w[v][u])) (v,u)∈E hzwer,miskcoo 图论及其应用 北京大学, 清华大学 36 / 75
  • 93.图论基础 图论算法 例题 单源最短路 Bellman-Ford 算法 这个算法主要是构造一个最短路径长度数组的序列：dist[1][u], dist[2][u], · · · , dist[n − 1][u]。 其中 dist[k][u] 表示从源 s 到 u 至多经过 k 条边的最短路径的长度。 显然我们可以得到这样的关系： dist[1][u] = w[s][u] dist[k][u] = min(dist[k − 1][u], min (dist[k − 1][v] + w[v][u])) (v,u)∈E 由于每次计算 dist 数组复杂度都是 O( E ) 的，总的复杂度就是 O( V E )。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 36 / 75
  • 94.图论基础 图论算法 例题 单源最短路 SPFA 算法 事实上，你会发现我们每次进行的计算可以看成是一次“松弛”。假设我 们现在已经得到了 Bellman-Ford 算法某个阶段的 dist 数组，然后我们发现 了一条 s 到 u 的距离比 dist[u] 更加短的路径。我们更新了 dist[u]。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 37 / 75
  • 95.图论基础 图论算法 例题 单源最短路 SPFA 算法 事实上，你会发现我们每次进行的计算可以看成是一次“松弛”。假设我 们现在已经得到了 Bellman-Ford 算法某个阶段的 dist 数组，然后我们发现 了一条 s 到 u 的距离比 dist[u] 更加短的路径。我们更新了 dist[u]。 那么接下来直接受到影响的就是与 u 直接关联的顶点 v，也就是如果 dist[u] + w[u][v] < dist[v] 的话，s 到 v 的最短路就可以利用 s 到 u 的最 短路加上 u 到 v 的边来更新。这样的话与 v 直接关联的顶点又会受到影响 ……不断这样持续下去直到最后没有顶点能被影响。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 37 / 75
  • 96.图论基础 图论算法 例题 单源最短路 SPFA 算法 事实上，你会发现我们每次进行的计算可以看成是一次“松弛”。假设我 们现在已经得到了 Bellman-Ford 算法某个阶段的 dist 数组，然后我们发现 了一条 s 到 u 的距离比 dist[u] 更加短的路径。我们更新了 dist[u]。 那么接下来直接受到影响的就是与 u 直接关联的顶点 v，也就是如果 dist[u] + w[u][v] < dist[v] 的话，s 到 v 的最短路就可以利用 s 到 u 的最 短路加上 u 到 v 的边来更新。这样的话与 v 直接关联的顶点又会受到影响 ……不断这样持续下去直到最后没有顶点能被影响。 那么一个优化就是我们利用队列存储这些需要更新的结点，每次从队列 中取出一个结点，计算是否有结点需要更新，如果有，并且这个结点不在队 列中，那么就将它加入队列。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 37 / 75
  • 97.图论基础 图论算法 例题 单源最短路 SPFA 算法 事实上，你会发现我们每次进行的计算可以看成是一次“松弛”。假设我 们现在已经得到了 Bellman-Ford 算法某个阶段的 dist 数组，然后我们发现 了一条 s 到 u 的距离比 dist[u] 更加短的路径。我们更新了 dist[u]。 那么接下来直接受到影响的就是与 u 直接关联的顶点 v，也就是如果 dist[u] + w[u][v] < dist[v] 的话，s 到 v 的最短路就可以利用 s 到 u 的最 短路加上 u 到 v 的边来更新。这样的话与 v 直接关联的顶点又会受到影响 ……不断这样持续下去直到最后没有顶点能被影响。 那么一个优化就是我们利用队列存储这些需要更新的结点，每次从队列 中取出一个结点，计算是否有结点需要更新，如果有，并且这个结点不在队 列中，那么就将它加入队列。 这样的算法被称为 SPFA——一种优化的 Bellman-Ford 算法。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 37 / 75
  • 98.图论基础 图论算法 例题 单源最短路 SPFA 算法 在竞赛中大多数人会选择用 SPFA 作为单源最段路的算法，主要原因在 于它比较好写，而且通常情况下跑得比较快。但是 SPFA 的复杂度实际上是 没有保证的，最坏情况基本和 Bellman-Ford 相同，但是最好的时候可以到 达 O( V + E )。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 38 / 75
  • 99.图论基础 图论算法 例题 单源最短路 SPFA 算法 在竞赛中大多数人会选择用 SPFA 作为单源最段路的算法，主要原因在 于它比较好写，而且通常情况下跑得比较快。但是 SPFA 的复杂度实际上是 没有保证的，最坏情况基本和 Bellman-Ford 相同，但是最好的时候可以到 达 O( V + E )。 非常重要的一点就是 SPFA 的队列需要使用 环队列，虽然最多队列里 只会有 n 各点，但是每个点可能会入队多次。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 38 / 75
  • 100.图论基础 图论算法 例题 单源最短路 SPFA 算法 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 39 / 75
  • 101.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 40 / 75
  • 102.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 事实上，Dijkstra 算法的思想和 Prim 有很多类似之处。Dijkstra 算法 维护了一个未访问的结点集合 T 以及一个从 s 到结点 u 的当前距离 dist[u]。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 40 / 75
  • 103.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 事实上，Dijkstra 算法的思想和 Prim 有很多类似之处。Dijkstra 算法 维护了一个未访问的结点集合 T 以及一个从 s 到结点 u 的当前距离 dist[u]。 1 将除源外所有结点当前距离设置为 ∞，将源 s 的当前距离设置为 0， 将当前节点设置为源 s。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 40 / 75
  • 104.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 事实上，Dijkstra 算法的思想和 Prim 有很多类似之处。Dijkstra 算法 维护了一个未访问的结点集合 T 以及一个从 s 到结点 u 的当前距离 dist[u]。 1 将除源外所有结点当前距离设置为 ∞，将源 s 的当前距离设置为 0， 将当前节点设置为源 s。 2 从当前结点 u 开始，找出所有在未访问集合 T 中与 u 有边 (u,v) 的结 点 v。如果 dist[u]+w[u][v]105.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 事实上，Dijkstra 算法的思想和 Prim 有很多类似之处。Dijkstra 算法 维护了一个未访问的结点集合 T 以及一个从 s 到结点 u 的当前距离 dist[u]。 1 将除源外所有结点当前距离设置为 ∞，将源 s 的当前距离设置为 0， 将当前节点设置为源 s。 2 从当前结点 u 开始，找出所有在未访问集合 T 中与 u 有边 (u,v) 的结 点 v。如果 dist[u]+w[u][v]106.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 事实上，Dijkstra 算法的思想和 Prim 有很多类似之处。Dijkstra 算法 维护了一个未访问的结点集合 T 以及一个从 s 到结点 u 的当前距离 dist[u]。 1 将除源外所有结点当前距离设置为 ∞，将源 s 的当前距离设置为 0， 将当前节点设置为源 s。 2 从当前结点 u 开始，找出所有在未访问集合 T 中与 u 有边 (u,v) 的结 点 v。如果 dist[u]+w[u][v]107.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 它的正确性在于，在未访问集合 T 中结点的 dist 是从 s 开始经过已经 访问集合中的结点到达它的最短路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 41 / 75108.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 它的正确性在于，在未访问集合 T 中结点的 dist 是从 s 开始经过已经 访问集合中的结点到达它的最短路。 如果选出的当前结点 u 的 dist 不是最终的最小值，那么它最终的最短 路一定是要经过一个此时 T 中的其它结点再到 u。这时那个结点的 dist 肯 定要小于 u 的 dist，这就和 u 是 dist 最小的结点矛盾了！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 41 / 75109.图论基础 图论算法 所有顶点间的最段路 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 42 / 75110.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75111.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75112.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75113.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 那么当加入了一个顶点 k 之后，最短路如果有变化的话一定是以 k 为中 间顶点，那么可以得到 d[k][i][j] = min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75114.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 那么当加入了一个顶点 k 之后，最短路如果有变化的话一定是以 k 为中 间顶点，那么可以得到 d[k][i][j] = min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j]) 这个算法的复杂度是 O( V 3)。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75115.图论基础 图论算法 例题 所有顶点间的最段路 例题 1 虫洞 给出由 n 个虫洞的质量，其由 m 条单向边连接。 虫洞之间跃迁需要一定燃料和 1 个单位时间，每过 1 单位时间虫洞反 色。 从白洞到黑洞，消耗的燃料减少 delta，反之燃料增加 delta（delta 为 两虫洞质量差）。 可以选择在一个结点花费 si 的时间停留一个单位时间。 求从虫洞 1 到 n 最小的燃料消耗。 其中 0 < n < 5000, 0 < m < 30000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 44 / 75116.图论基础 图论算法 所有顶点间的最段路 每个点拆成黑白两个 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 45 / 75117.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75118.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta 其余连边同理 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75119.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta 其余连边同理 求最短路 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75120.图论基础 图论算法 例题 所有顶点间的最段路 例题 2 BZOJ2143 给出两个 n ∗ m 的矩阵 A，B，以及 3 个人的坐标 在 (i, j) 支付 Ai,j 的费用可以弹射到曼哈顿距离不超过 Bi,j 的位置 问三个人汇合所需要的最小总费用 其中 0 < n, m < 150, 0 < A < 1000, 0 < B < 109。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 46 / 75121.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75122.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75123.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 每走一格消耗 1 的能量，f(i, j, k) 表示在 (i, j) 且有 k 的能量的最少费 用 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75124.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 每走一格消耗 1 的能量，f(i, j, k) 表示在 (i, j) 且有 k 的能量的最少费 用 求三次最短路，枚举汇合点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75125.图论基础 图论算法 有向图的强连通分量 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 48 / 75126.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75127.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 9 6 8 5 4 3 7 12 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75128.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 9 6 8 5 4 3 7 12 比如说这个有向图中，点 1, 2, 4, 5, 6, 7, 8 和相应边组成的子图就是一 个强连通分量，另外点 3, 9 单独构成强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75129.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75130.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75131.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75132.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75133.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇 到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成 的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75134.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇 到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成 hzwer,m的iskc。oo 除此之外，像从结点 1 到结点 6 这样的边叫做前向边（forward 北京大学, 清华大学 图论及其应用 50 / 75135.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的 算法。它可以在 O( V + E ) 的时间内得出结果。 Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 51 / 75136.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的 算法。它可以在 O( V + E ) 的时间内得出结果。 Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。 很重要的一点是如果结点 u 是某个强连通分量在搜索树中遇到的第一个 结点（这通常被称为这个强连通分量的根）。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 51 / 75137.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75138.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75139.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75140.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75141.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 显然通过反祖边到达的结点 v 满足 low 的性质，但是通过横叉边到达 的却不一定。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75142.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 显然通过反祖边到达的结点 v 满足 low 的性质，但是通过横叉边到达 的却不一定。 可以证明，结点 u 是某个强连通分量的根等价于 dfn[u] 和 low[u] 相等。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75143.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75144.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： 1◦ 结点 u 通过树边到达结点 v low[u] = min(low[u], low[v]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75145.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： 1◦ 结点 u 通过树边到达结点 v low[u] = min(low[u], low[v]) 2◦ 结点 u 通过反祖边到达结点 v，或者通过横叉边到达结点 v 并且满 足 low 定义中 v 的性质 low[u] = min(low[u], dfn[v]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75146.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75147.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 如何更新 low？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75148.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 如何更新 low？ 关键就在于第二种情况，当通过反祖边或者横叉边走到一个结点的时 候，只需要判断这个结点是否在栈中，如果在就用它的 low 值更新当前节 点的 low 值，否则就不更新。因为如果不在栈中这个结点就已经确定在某个 强连通分量中了，不可能回到 u。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75149.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 具体参见我的 hzwer,miskcoo 。 图论及其应用 北京大学, 清华大学 55 / 75150.图论基础 图论算法 无向图的双连通分量、割点与桥 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 56 / 75151.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 在图论中，如果在一个无向连通图中删除一个结点及与它相关的边之 后，该图被分成两个或者更多的连通分量，那么这个点就被称为割点（cut vertex），也被称为关节点（articulation vertex）。如果一个无向连通图没 有割点，那么就称该图为点双连通图。无向图的极大点双连通子图被称为点 双连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 57 / 75152.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 在图论中，如果在一个无向连通图中删除一个结点及与它相关的边之 后，该图被分成两个或者更多的连通分量，那么这个点就被称为割点（cut vertex），也被称为关节点（articulation vertex）。如果一个无向连通图没 有割点，那么就称该图为点双连通图。无向图的极大点双连通子图被称为点 双连通分量。 如果在一个无向连通图中删除一条边后，该图被分成两个或者更多的连 通分量，那么这条边就被称为割边（cut edge），也被称为桥（bridge）。如 果一个无向连通图没有割边，那么就称该图为边双连通图。无向图的极大边 双连通子图被称为边双连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 57 / 75153.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75154.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75155.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 如果结点 u 不是搜索树的根，那么当存在 v 是 u 的儿子并且并且满足 dfn[u] ≤ low[v]，那么结点 u 也是割点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75156.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 如果结点 u 不是搜索树的根，那么当存在 v 是 u 的儿子并且并且满足 dfn[u] ≤ low[v]，那么结点 u 也是割点。 至于割边，上面不等式改成小于号即可。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75157.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75158.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75159.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75160.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 选择度数为 m-(n-2) 的非割点结点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75161.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 选择度数为 m-(n-2) 的非割点结点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75162.图论基础 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 60 / 75163.图论基础 例题. 混合图 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 61 / 75164.图论基础 图论算法 例题 例题. 混合图 混合图 你有一个混合图，它有 n 个顶点，m 条边，其中 a 条是有向边，b 条 是无向边。现在要求为这 b 条无向边确定一个方向，使得最后的有向图上不 存在环。 其中 1 ≤ n, a, b ≤ 105, m = a + b。不用考虑无解的情况。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 62 / 75165.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75166.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75167.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。 先把无向边忽略，对图进行拓扑排序，最后无向边的方向就是拓扑序小 的连向拓扑序大的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75168.图论基础 例题. 灾后重建 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 64 / 75169.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对 公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公 路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通 车，只能到达重建完成的村庄。 给出 B 地区的村庄数 n，村庄编号从 1 到 n，和所有 m 条公路的长度， 公路是双向的。并给出第 i 个村庄重建完成的时间 t[i]，你可以认为是同时 开始重建并在第 t[i] 天重建完成，并且在当天即可通车。若 t[i] 为 0 则说明 地震未对此地区造成损坏，一开始就可以通车。之后有 Q 个询问 (x, y, t)， 对于每个询问你要回答在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多 少。如果无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村 庄，或者村庄 x 或村庄 y 在第 t 天仍未重建完成，则需要返回-1。 数据保证 t[1]≤t[2]≤ · · · ≤t[n]。并且 0 < n ≤ 200, 0 < Q ≤ 50000。 Source：福建 NOIP 夏令营 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 65 / 75170.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75171.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 最短路只能经过前 i 个村庄。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75172.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 最短路只能经过前 i 个村庄。 Floyd！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75173.图论基础 例题. 肮脏的道路 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 67 / 75174.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 有一个 n 个结点 m 条边的无向图，边有权值。 从一个结点 s 到另一个结点 t 的一条路径的肮脏值定义为路径上权值最 大的那条边的权值。 要求计算出从 s 到 t 的所有路径中肮脏值最小的那条路径的肮脏值。 其中 1 ≤ n ≤ 10000, 1 ≤ m ≤ 20000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 68 / 75175.图论基础 图论算法 例题. 肮脏的道路 肮脏的道路 二分？ hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 69 / 75176.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 二分？ 类似 Kruskal 算法直接判断连通。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 69 / 75177.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 二分？ 类似 Kruskal 算法直接判断连通。 事实上，这样的路径叫做最小 路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 69 / 75178.图论基础 例题. Candies 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 70 / 75179.图论基础 图论算法 例题 例题. Candies Candies 有 n 个人分糖果，现在有 m 个限制，比如说某一个人得到的糖果不能 比另一个人少 k 个以上。 请你求出小 A 比小 B 最多能多得到多少个糖果。 其中 1 ≤ n ≤ 30000, 1 ≤ m ≤ 150000。 Source：POJ 3159. Candies hzwer,miskcoo 图论及其应用 北京大学, 清华大学 71 / 75180.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75181.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k 将每个人看成一个点，比如上面这个限制就从 B 向 A 连接一条长度为 k 的边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75182.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k 将每个人看成一个点，比如上面这个限制就从 B 向 A 连接一条长度为 k 的边。 最短路 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75183.图论基础 例题. 和平委员会 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 73 / 75184.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 某国有 n 个党派，每个党派在议会中恰有 2 个代表。有 m 对代表之间 会有矛盾存在。 现在要成立和平委员会，该会满足： • 每个党派在和平委员会中有且只有一个代表。 • 如果某两个代表存在矛盾，则他们不能都属于委员会。 判断是否能够成立这个委员会。如果能，给出方案。 其中 1 ≤ n ≤ 8000, 1 ≤ m ≤ 20000。 Source：Poi 0106 Peaceful Commission hzwer,miskcoo 图论及其应用 北京大学, 清华大学 74 / 75185.图论基础 图论算法 例题. 和平委员会 和平委员会 将每个代表看成一个点。 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 75 / 75186.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75187.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 若一个党派的人在一个环内无解！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75188.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 若一个党派的人在一个环内无解！ 缩环！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75189.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75190.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75191.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75192.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75193.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75194.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75195.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 按照拓扑序来找点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75196.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 按照拓扑序来找点。 这个问题实际上被称为 2-SAT 问题。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 105.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 事实上，Dijkstra 算法的思想和 Prim 有很多类似之处。Dijkstra 算法 维护了一个未访问的结点集合 T 以及一个从 s 到结点 u 的当前距离 dist[u]。 1 将除源外所有结点当前距离设置为 ∞，将源 s 的当前距离设置为 0， 将当前节点设置为源 s。 2 从当前结点 u 开始，找出所有在未访问集合 T 中与 u 有边 (u,v) 的结 点 v。如果 dist[u]+w[u][v]106.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 事实上，Dijkstra 算法的思想和 Prim 有很多类似之处。Dijkstra 算法 维护了一个未访问的结点集合 T 以及一个从 s 到结点 u 的当前距离 dist[u]。 1 将除源外所有结点当前距离设置为 ∞，将源 s 的当前距离设置为 0， 将当前节点设置为源 s。 2 从当前结点 u 开始，找出所有在未访问集合 T 中与 u 有边 (u,v) 的结 点 v。如果 dist[u]+w[u][v]107.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 它的正确性在于，在未访问集合 T 中结点的 dist 是从 s 开始经过已经 访问集合中的结点到达它的最短路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 41 / 75108.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 它的正确性在于，在未访问集合 T 中结点的 dist 是从 s 开始经过已经 访问集合中的结点到达它的最短路。 如果选出的当前结点 u 的 dist 不是最终的最小值，那么它最终的最短 路一定是要经过一个此时 T 中的其它结点再到 u。这时那个结点的 dist 肯 定要小于 u 的 dist，这就和 u 是 dist 最小的结点矛盾了！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 41 / 75109.图论基础 图论算法 所有顶点间的最段路 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 42 / 75110.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75111.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75112.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75113.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 那么当加入了一个顶点 k 之后，最短路如果有变化的话一定是以 k 为中 间顶点，那么可以得到 d[k][i][j] = min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75114.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 那么当加入了一个顶点 k 之后，最短路如果有变化的话一定是以 k 为中 间顶点，那么可以得到 d[k][i][j] = min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j]) 这个算法的复杂度是 O( V 3)。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75115.图论基础 图论算法 例题 所有顶点间的最段路 例题 1 虫洞 给出由 n 个虫洞的质量，其由 m 条单向边连接。 虫洞之间跃迁需要一定燃料和 1 个单位时间，每过 1 单位时间虫洞反 色。 从白洞到黑洞，消耗的燃料减少 delta，反之燃料增加 delta（delta 为 两虫洞质量差）。 可以选择在一个结点花费 si 的时间停留一个单位时间。 求从虫洞 1 到 n 最小的燃料消耗。 其中 0 < n < 5000, 0 < m < 30000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 44 / 75116.图论基础 图论算法 所有顶点间的最段路 每个点拆成黑白两个 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 45 / 75117.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75118.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta 其余连边同理 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75119.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta 其余连边同理 求最短路 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75120.图论基础 图论算法 例题 所有顶点间的最段路 例题 2 BZOJ2143 给出两个 n ∗ m 的矩阵 A，B，以及 3 个人的坐标 在 (i, j) 支付 Ai,j 的费用可以弹射到曼哈顿距离不超过 Bi,j 的位置 问三个人汇合所需要的最小总费用 其中 0 < n, m < 150, 0 < A < 1000, 0 < B < 109。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 46 / 75121.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75122.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75123.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 每走一格消耗 1 的能量，f(i, j, k) 表示在 (i, j) 且有 k 的能量的最少费 用 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75124.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 每走一格消耗 1 的能量，f(i, j, k) 表示在 (i, j) 且有 k 的能量的最少费 用 求三次最短路，枚举汇合点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75125.图论基础 图论算法 有向图的强连通分量 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 48 / 75126.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75127.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 9 6 8 5 4 3 7 12 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75128.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 9 6 8 5 4 3 7 12 比如说这个有向图中，点 1, 2, 4, 5, 6, 7, 8 和相应边组成的子图就是一 个强连通分量，另外点 3, 9 单独构成强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75129.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75130.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75131.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75132.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75133.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇 到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成 的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75134.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇 到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成 hzwer,m的iskc。oo 除此之外，像从结点 1 到结点 6 这样的边叫做前向边（forward 北京大学, 清华大学 图论及其应用 50 / 75135.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的 算法。它可以在 O( V + E ) 的时间内得出结果。 Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 51 / 75136.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的 算法。它可以在 O( V + E ) 的时间内得出结果。 Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。 很重要的一点是如果结点 u 是某个强连通分量在搜索树中遇到的第一个 结点（这通常被称为这个强连通分量的根）。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 51 / 75137.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75138.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75139.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75140.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75141.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 显然通过反祖边到达的结点 v 满足 low 的性质，但是通过横叉边到达 的却不一定。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75142.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 显然通过反祖边到达的结点 v 满足 low 的性质，但是通过横叉边到达 的却不一定。 可以证明，结点 u 是某个强连通分量的根等价于 dfn[u] 和 low[u] 相等。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75143.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75144.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： 1◦ 结点 u 通过树边到达结点 v low[u] = min(low[u], low[v]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75145.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： 1◦ 结点 u 通过树边到达结点 v low[u] = min(low[u], low[v]) 2◦ 结点 u 通过反祖边到达结点 v，或者通过横叉边到达结点 v 并且满 足 low 定义中 v 的性质 low[u] = min(low[u], dfn[v]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75146.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75147.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 如何更新 low？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75148.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 如何更新 low？ 关键就在于第二种情况，当通过反祖边或者横叉边走到一个结点的时 候，只需要判断这个结点是否在栈中，如果在就用它的 low 值更新当前节 点的 low 值，否则就不更新。因为如果不在栈中这个结点就已经确定在某个 强连通分量中了，不可能回到 u。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75149.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 具体参见我的 hzwer,miskcoo 。 图论及其应用 北京大学, 清华大学 55 / 75150.图论基础 图论算法 无向图的双连通分量、割点与桥 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 56 / 75151.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 在图论中，如果在一个无向连通图中删除一个结点及与它相关的边之 后，该图被分成两个或者更多的连通分量，那么这个点就被称为割点（cut vertex），也被称为关节点（articulation vertex）。如果一个无向连通图没 有割点，那么就称该图为点双连通图。无向图的极大点双连通子图被称为点 双连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 57 / 75152.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 在图论中，如果在一个无向连通图中删除一个结点及与它相关的边之 后，该图被分成两个或者更多的连通分量，那么这个点就被称为割点（cut vertex），也被称为关节点（articulation vertex）。如果一个无向连通图没 有割点，那么就称该图为点双连通图。无向图的极大点双连通子图被称为点 双连通分量。 如果在一个无向连通图中删除一条边后，该图被分成两个或者更多的连 通分量，那么这条边就被称为割边（cut edge），也被称为桥（bridge）。如 果一个无向连通图没有割边，那么就称该图为边双连通图。无向图的极大边 双连通子图被称为边双连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 57 / 75153.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75154.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75155.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 如果结点 u 不是搜索树的根，那么当存在 v 是 u 的儿子并且并且满足 dfn[u] ≤ low[v]，那么结点 u 也是割点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75156.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 如果结点 u 不是搜索树的根，那么当存在 v 是 u 的儿子并且并且满足 dfn[u] ≤ low[v]，那么结点 u 也是割点。 至于割边，上面不等式改成小于号即可。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75157.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75158.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75159.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75160.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 选择度数为 m-(n-2) 的非割点结点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75161.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 选择度数为 m-(n-2) 的非割点结点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75162.图论基础 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 60 / 75163.图论基础 例题. 混合图 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 61 / 75164.图论基础 图论算法 例题 例题. 混合图 混合图 你有一个混合图，它有 n 个顶点，m 条边，其中 a 条是有向边，b 条 是无向边。现在要求为这 b 条无向边确定一个方向，使得最后的有向图上不 存在环。 其中 1 ≤ n, a, b ≤ 105, m = a + b。不用考虑无解的情况。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 62 / 75165.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75166.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75167.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。 先把无向边忽略，对图进行拓扑排序，最后无向边的方向就是拓扑序小 的连向拓扑序大的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75168.图论基础 例题. 灾后重建 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 64 / 75169.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对 公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公 路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通 车，只能到达重建完成的村庄。 给出 B 地区的村庄数 n，村庄编号从 1 到 n，和所有 m 条公路的长度， 公路是双向的。并给出第 i 个村庄重建完成的时间 t[i]，你可以认为是同时 开始重建并在第 t[i] 天重建完成，并且在当天即可通车。若 t[i] 为 0 则说明 地震未对此地区造成损坏，一开始就可以通车。之后有 Q 个询问 (x, y, t)， 对于每个询问你要回答在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多 少。如果无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村 庄，或者村庄 x 或村庄 y 在第 t 天仍未重建完成，则需要返回-1。 数据保证 t[1]≤t[2]≤ · · · ≤t[n]。并且 0 < n ≤ 200, 0 < Q ≤ 50000。 Source：福建 NOIP 夏令营 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 65 / 75170.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75171.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 最短路只能经过前 i 个村庄。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75172.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 最短路只能经过前 i 个村庄。 Floyd！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75173.图论基础 例题. 肮脏的道路 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 67 / 75174.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 有一个 n 个结点 m 条边的无向图，边有权值。 从一个结点 s 到另一个结点 t 的一条路径的肮脏值定义为路径上权值最 大的那条边的权值。 要求计算出从 s 到 t 的所有路径中肮脏值最小的那条路径的肮脏值。 其中 1 ≤ n ≤ 10000, 1 ≤ m ≤ 20000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 68 / 75175.图论基础 图论算法 例题. 肮脏的道路 肮脏的道路 二分？ hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 69 / 75176.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 二分？ 类似 Kruskal 算法直接判断连通。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 69 / 75177.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 二分？ 类似 Kruskal 算法直接判断连通。 事实上，这样的路径叫做最小 路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 69 / 75178.图论基础 例题. Candies 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 70 / 75179.图论基础 图论算法 例题 例题. Candies Candies 有 n 个人分糖果，现在有 m 个限制，比如说某一个人得到的糖果不能 比另一个人少 k 个以上。 请你求出小 A 比小 B 最多能多得到多少个糖果。 其中 1 ≤ n ≤ 30000, 1 ≤ m ≤ 150000。 Source：POJ 3159. Candies hzwer,miskcoo 图论及其应用 北京大学, 清华大学 71 / 75180.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75181.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k 将每个人看成一个点，比如上面这个限制就从 B 向 A 连接一条长度为 k 的边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75182.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k 将每个人看成一个点，比如上面这个限制就从 B 向 A 连接一条长度为 k 的边。 最短路 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75183.图论基础 例题. 和平委员会 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 73 / 75184.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 某国有 n 个党派，每个党派在议会中恰有 2 个代表。有 m 对代表之间 会有矛盾存在。 现在要成立和平委员会，该会满足： • 每个党派在和平委员会中有且只有一个代表。 • 如果某两个代表存在矛盾，则他们不能都属于委员会。 判断是否能够成立这个委员会。如果能，给出方案。 其中 1 ≤ n ≤ 8000, 1 ≤ m ≤ 20000。 Source：Poi 0106 Peaceful Commission hzwer,miskcoo 图论及其应用 北京大学, 清华大学 74 / 75185.图论基础 图论算法 例题. 和平委员会 和平委员会 将每个代表看成一个点。 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 75 / 75186.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75187.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 若一个党派的人在一个环内无解！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75188.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 若一个党派的人在一个环内无解！ 缩环！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75189.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75190.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75191.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75192.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75193.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75194.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75195.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 按照拓扑序来找点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75196.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 按照拓扑序来找点。 这个问题实际上被称为 2-SAT 问题。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 106.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 如果有向图的边权值全为正数，那么有一种复杂度有保证的单源最段路 算法——Dijkstra 算法。它的复杂度是 O( E log V )。 事实上，Dijkstra 算法的思想和 Prim 有很多类似之处。Dijkstra 算法 维护了一个未访问的结点集合 T 以及一个从 s 到结点 u 的当前距离 dist[u]。 1 将除源外所有结点当前距离设置为 ∞，将源 s 的当前距离设置为 0， 将当前节点设置为源 s。 2 从当前结点 u 开始，找出所有在未访问集合 T 中与 u 有边 (u,v) 的结 点 v。如果 dist[u]+w[u][v]107.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 它的正确性在于，在未访问集合 T 中结点的 dist 是从 s 开始经过已经 访问集合中的结点到达它的最短路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 41 / 75108.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 它的正确性在于，在未访问集合 T 中结点的 dist 是从 s 开始经过已经 访问集合中的结点到达它的最短路。 如果选出的当前结点 u 的 dist 不是最终的最小值，那么它最终的最短 路一定是要经过一个此时 T 中的其它结点再到 u。这时那个结点的 dist 肯 定要小于 u 的 dist，这就和 u 是 dist 最小的结点矛盾了！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 41 / 75109.图论基础 图论算法 所有顶点间的最段路 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 42 / 75110.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75111.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75112.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75113.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 那么当加入了一个顶点 k 之后，最短路如果有变化的话一定是以 k 为中 间顶点，那么可以得到 d[k][i][j] = min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75114.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 那么当加入了一个顶点 k 之后，最短路如果有变化的话一定是以 k 为中 间顶点，那么可以得到 d[k][i][j] = min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j]) 这个算法的复杂度是 O( V 3)。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75115.图论基础 图论算法 例题 所有顶点间的最段路 例题 1 虫洞 给出由 n 个虫洞的质量，其由 m 条单向边连接。 虫洞之间跃迁需要一定燃料和 1 个单位时间，每过 1 单位时间虫洞反 色。 从白洞到黑洞，消耗的燃料减少 delta，反之燃料增加 delta（delta 为 两虫洞质量差）。 可以选择在一个结点花费 si 的时间停留一个单位时间。 求从虫洞 1 到 n 最小的燃料消耗。 其中 0 < n < 5000, 0 < m < 30000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 44 / 75116.图论基础 图论算法 所有顶点间的最段路 每个点拆成黑白两个 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 45 / 75117.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75118.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta 其余连边同理 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75119.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta 其余连边同理 求最短路 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75120.图论基础 图论算法 例题 所有顶点间的最段路 例题 2 BZOJ2143 给出两个 n ∗ m 的矩阵 A，B，以及 3 个人的坐标 在 (i, j) 支付 Ai,j 的费用可以弹射到曼哈顿距离不超过 Bi,j 的位置 问三个人汇合所需要的最小总费用 其中 0 < n, m < 150, 0 < A < 1000, 0 < B < 109。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 46 / 75121.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75122.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75123.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 每走一格消耗 1 的能量，f(i, j, k) 表示在 (i, j) 且有 k 的能量的最少费 用 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75124.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 每走一格消耗 1 的能量，f(i, j, k) 表示在 (i, j) 且有 k 的能量的最少费 用 求三次最短路，枚举汇合点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75125.图论基础 图论算法 有向图的强连通分量 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 48 / 75126.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75127.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 9 6 8 5 4 3 7 12 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75128.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 9 6 8 5 4 3 7 12 比如说这个有向图中，点 1, 2, 4, 5, 6, 7, 8 和相应边组成的子图就是一 个强连通分量，另外点 3, 9 单独构成强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75129.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75130.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75131.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75132.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75133.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇 到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成 的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75134.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇 到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成 hzwer,m的iskc。oo 除此之外，像从结点 1 到结点 6 这样的边叫做前向边（forward 北京大学, 清华大学 图论及其应用 50 / 75135.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的 算法。它可以在 O( V + E ) 的时间内得出结果。 Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 51 / 75136.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的 算法。它可以在 O( V + E ) 的时间内得出结果。 Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。 很重要的一点是如果结点 u 是某个强连通分量在搜索树中遇到的第一个 结点（这通常被称为这个强连通分量的根）。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 51 / 75137.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75138.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75139.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75140.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75141.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 显然通过反祖边到达的结点 v 满足 low 的性质，但是通过横叉边到达 的却不一定。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75142.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 显然通过反祖边到达的结点 v 满足 low 的性质，但是通过横叉边到达 的却不一定。 可以证明，结点 u 是某个强连通分量的根等价于 dfn[u] 和 low[u] 相等。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75143.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75144.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： 1◦ 结点 u 通过树边到达结点 v low[u] = min(low[u], low[v]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75145.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： 1◦ 结点 u 通过树边到达结点 v low[u] = min(low[u], low[v]) 2◦ 结点 u 通过反祖边到达结点 v，或者通过横叉边到达结点 v 并且满 足 low 定义中 v 的性质 low[u] = min(low[u], dfn[v]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75146.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75147.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 如何更新 low？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75148.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 如何更新 low？ 关键就在于第二种情况，当通过反祖边或者横叉边走到一个结点的时 候，只需要判断这个结点是否在栈中，如果在就用它的 low 值更新当前节 点的 low 值，否则就不更新。因为如果不在栈中这个结点就已经确定在某个 强连通分量中了，不可能回到 u。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75149.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 具体参见我的 hzwer,miskcoo 。 图论及其应用 北京大学, 清华大学 55 / 75150.图论基础 图论算法 无向图的双连通分量、割点与桥 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 56 / 75151.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 在图论中，如果在一个无向连通图中删除一个结点及与它相关的边之 后，该图被分成两个或者更多的连通分量，那么这个点就被称为割点（cut vertex），也被称为关节点（articulation vertex）。如果一个无向连通图没 有割点，那么就称该图为点双连通图。无向图的极大点双连通子图被称为点 双连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 57 / 75152.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 在图论中，如果在一个无向连通图中删除一个结点及与它相关的边之 后，该图被分成两个或者更多的连通分量，那么这个点就被称为割点（cut vertex），也被称为关节点（articulation vertex）。如果一个无向连通图没 有割点，那么就称该图为点双连通图。无向图的极大点双连通子图被称为点 双连通分量。 如果在一个无向连通图中删除一条边后，该图被分成两个或者更多的连 通分量，那么这条边就被称为割边（cut edge），也被称为桥（bridge）。如 果一个无向连通图没有割边，那么就称该图为边双连通图。无向图的极大边 双连通子图被称为边双连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 57 / 75153.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75154.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75155.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 如果结点 u 不是搜索树的根，那么当存在 v 是 u 的儿子并且并且满足 dfn[u] ≤ low[v]，那么结点 u 也是割点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75156.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 如果结点 u 不是搜索树的根，那么当存在 v 是 u 的儿子并且并且满足 dfn[u] ≤ low[v]，那么结点 u 也是割点。 至于割边，上面不等式改成小于号即可。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75157.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75158.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75159.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75160.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 选择度数为 m-(n-2) 的非割点结点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75161.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 选择度数为 m-(n-2) 的非割点结点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75162.图论基础 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 60 / 75163.图论基础 例题. 混合图 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 61 / 75164.图论基础 图论算法 例题 例题. 混合图 混合图 你有一个混合图，它有 n 个顶点，m 条边，其中 a 条是有向边，b 条 是无向边。现在要求为这 b 条无向边确定一个方向，使得最后的有向图上不 存在环。 其中 1 ≤ n, a, b ≤ 105, m = a + b。不用考虑无解的情况。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 62 / 75165.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75166.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75167.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。 先把无向边忽略，对图进行拓扑排序，最后无向边的方向就是拓扑序小 的连向拓扑序大的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75168.图论基础 例题. 灾后重建 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 64 / 75169.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对 公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公 路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通 车，只能到达重建完成的村庄。 给出 B 地区的村庄数 n，村庄编号从 1 到 n，和所有 m 条公路的长度， 公路是双向的。并给出第 i 个村庄重建完成的时间 t[i]，你可以认为是同时 开始重建并在第 t[i] 天重建完成，并且在当天即可通车。若 t[i] 为 0 则说明 地震未对此地区造成损坏，一开始就可以通车。之后有 Q 个询问 (x, y, t)， 对于每个询问你要回答在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多 少。如果无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村 庄，或者村庄 x 或村庄 y 在第 t 天仍未重建完成，则需要返回-1。 数据保证 t[1]≤t[2]≤ · · · ≤t[n]。并且 0 < n ≤ 200, 0 < Q ≤ 50000。 Source：福建 NOIP 夏令营 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 65 / 75170.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75171.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 最短路只能经过前 i 个村庄。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75172.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 最短路只能经过前 i 个村庄。 Floyd！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75173.图论基础 例题. 肮脏的道路 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 67 / 75174.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 有一个 n 个结点 m 条边的无向图，边有权值。 从一个结点 s 到另一个结点 t 的一条路径的肮脏值定义为路径上权值最 大的那条边的权值。 要求计算出从 s 到 t 的所有路径中肮脏值最小的那条路径的肮脏值。 其中 1 ≤ n ≤ 10000, 1 ≤ m ≤ 20000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 68 / 75175.图论基础 图论算法 例题. 肮脏的道路 肮脏的道路 二分？ hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 69 / 75176.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 二分？ 类似 Kruskal 算法直接判断连通。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 69 / 75177.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 二分？ 类似 Kruskal 算法直接判断连通。 事实上，这样的路径叫做最小 路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 69 / 75178.图论基础 例题. Candies 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 70 / 75179.图论基础 图论算法 例题 例题. Candies Candies 有 n 个人分糖果，现在有 m 个限制，比如说某一个人得到的糖果不能 比另一个人少 k 个以上。 请你求出小 A 比小 B 最多能多得到多少个糖果。 其中 1 ≤ n ≤ 30000, 1 ≤ m ≤ 150000。 Source：POJ 3159. Candies hzwer,miskcoo 图论及其应用 北京大学, 清华大学 71 / 75180.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75181.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k 将每个人看成一个点，比如上面这个限制就从 B 向 A 连接一条长度为 k 的边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75182.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k 将每个人看成一个点，比如上面这个限制就从 B 向 A 连接一条长度为 k 的边。 最短路 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75183.图论基础 例题. 和平委员会 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 73 / 75184.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 某国有 n 个党派，每个党派在议会中恰有 2 个代表。有 m 对代表之间 会有矛盾存在。 现在要成立和平委员会，该会满足： • 每个党派在和平委员会中有且只有一个代表。 • 如果某两个代表存在矛盾，则他们不能都属于委员会。 判断是否能够成立这个委员会。如果能，给出方案。 其中 1 ≤ n ≤ 8000, 1 ≤ m ≤ 20000。 Source：Poi 0106 Peaceful Commission hzwer,miskcoo 图论及其应用 北京大学, 清华大学 74 / 75185.图论基础 图论算法 例题. 和平委员会 和平委员会 将每个代表看成一个点。 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 75 / 75186.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75187.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 若一个党派的人在一个环内无解！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75188.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 若一个党派的人在一个环内无解！ 缩环！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75189.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75190.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75191.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75192.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75193.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75194.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75195.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 按照拓扑序来找点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75196.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 按照拓扑序来找点。 这个问题实际上被称为 2-SAT 问题。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 107.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 它的正确性在于，在未访问集合 T 中结点的 dist 是从 s 开始经过已经 访问集合中的结点到达它的最短路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 41 / 75
  • 108.图论基础 图论算法 例题 单源最短路 Dijkstra 算法 它的正确性在于，在未访问集合 T 中结点的 dist 是从 s 开始经过已经 访问集合中的结点到达它的最短路。 如果选出的当前结点 u 的 dist 不是最终的最小值，那么它最终的最短 路一定是要经过一个此时 T 中的其它结点再到 u。这时那个结点的 dist 肯 定要小于 u 的 dist，这就和 u 是 dist 最小的结点矛盾了！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 41 / 75
  • 109.图论基础 图论算法 所有顶点间的最段路 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 42 / 75
  • 110.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75
  • 111.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75
  • 112.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75
  • 113.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 那么当加入了一个顶点 k 之后，最短路如果有变化的话一定是以 k 为中 间顶点，那么可以得到 d[k][i][j] = min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75
  • 114.图论基础 图论算法 例题 所有顶点间的最段路 Floyd 算法 如果你要求所有顶点间的最短路，当然可以对每个顶点跑单源最短路。 但是，有一个更为直接的 Floyd 算法。 我们设 d[k][i][j] 为除了 i 和 j 外只经过前 k 个结点，从 i 到 j 的最短路。 显然可以知道 d[0][i][j] = w[i][j]。 那么当加入了一个顶点 k 之后，最短路如果有变化的话一定是以 k 为中 间顶点，那么可以得到 d[k][i][j] = min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j]) 这个算法的复杂度是 O( V 3)。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 43 / 75
  • 115.图论基础 图论算法 例题 所有顶点间的最段路 例题 1 虫洞 给出由 n 个虫洞的质量，其由 m 条单向边连接。 虫洞之间跃迁需要一定燃料和 1 个单位时间，每过 1 单位时间虫洞反 色。 从白洞到黑洞，消耗的燃料减少 delta，反之燃料增加 delta（delta 为 两虫洞质量差）。 可以选择在一个结点花费 si 的时间停留一个单位时间。 求从虫洞 1 到 n 最小的燃料消耗。 其中 0 < n < 5000, 0 < m < 30000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 44 / 75
  • 116.图论基础 图论算法 所有顶点间的最段路 每个点拆成黑白两个 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 45 / 75
  • 117.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75
  • 118.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta 其余连边同理 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75
  • 119.图论基础 图论算法 所有顶点间的最段路 例题 每个点拆成黑白两个 由于每秒虫洞变色，所以黑点之间边权为 v + delta 其余连边同理 求最短路 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 45 / 75
  • 120.图论基础 图论算法 例题 所有顶点间的最段路 例题 2 BZOJ2143 给出两个 n ∗ m 的矩阵 A，B，以及 3 个人的坐标 在 (i, j) 支付 Ai,j 的费用可以弹射到曼哈顿距离不超过 Bi,j 的位置 问三个人汇合所需要的最小总费用 其中 0 < n, m < 150, 0 < A < 1000, 0 < B < 109。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 46 / 75
  • 121.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75
  • 122.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75
  • 123.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 每走一格消耗 1 的能量，f(i, j, k) 表示在 (i, j) 且有 k 的能量的最少费 用 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75
  • 124.图论基础 图论算法 所有顶点间的最段路 例题 这道题点很少，但是边可能很多，直接建图做最短路显然不可行 把弹射看成获得了可以走 ai,j 的能量 每走一格消耗 1 的能量，f(i, j, k) 表示在 (i, j) 且有 k 的能量的最少费 用 求三次最短路，枚举汇合点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 47 / 75
  • 125.图论基础 图论算法 有向图的强连通分量 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 48 / 75
  • 126.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75
  • 127.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 9 6 8 5 4 3 7 12 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75
  • 128.图论基础 图论算法 例题 有向图的强连通分量 有向图的强连通分量 在图论中，一个有向图被成为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连 通子图（这里指点数极大）被称为强连通分量。 9 6 8 5 4 3 7 12 比如说这个有向图中，点 1, 2, 4, 5, 6, 7, 8 和相应边组成的子图就是一 个强连通分量，另外点 3, 9 单独构成强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 49 / 75
  • 129.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75
  • 130.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75
  • 131.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75
  • 132.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75
  • 133.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇 到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成 的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 50 / 75
  • 134.图论基础 图论算法 例题 有向图的强连通分量 搜索树 在介绍求解强连通分量的算法之前先来介绍一下搜索树。 1 2 5 3 4 6 7 8 9 有向图的搜索树主要有 4 种边（这张图只有三种），其中用实线画出来 的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就 形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回 边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇 到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成 hzwer,m的iskc。oo 除此之外，像从结点 1 到结点 6 这样的边叫做前向边（forward 北京大学, 清华大学 图论及其应用 50 / 75
  • 135.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的 算法。它可以在 O( V + E ) 的时间内得出结果。 Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 51 / 75
  • 136.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的 算法。它可以在 O( V + E ) 的时间内得出结果。 Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。 很重要的一点是如果结点 u 是某个强连通分量在搜索树中遇到的第一个 结点（这通常被称为这个强连通分量的根）。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 51 / 75
  • 137.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75
  • 138.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75
  • 139.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75
  • 140.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75
  • 141.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 显然通过反祖边到达的结点 v 满足 low 的性质，但是通过横叉边到达 的却不一定。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75
  • 142.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn、low 和一个 栈。 • 栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分 量的结点。 • dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间 戳。 • low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再 通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳， 并且要求 v 有一些额外的性质：v 还要能够到达 u。 显然通过反祖边到达的结点 v 满足 low 的性质，但是通过横叉边到达 的却不一定。 可以证明，结点 u 是某个强连通分量的根等价于 dfn[u] 和 low[u] 相等。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 52 / 75
  • 143.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75
  • 144.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： 1◦ 结点 u 通过树边到达结点 v low[u] = min(low[u], low[v]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75
  • 145.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 当通过 u 搜索到一个新的节点 v 的时候可以有多种情况： 1◦ 结点 u 通过树边到达结点 v low[u] = min(low[u], low[v]) 2◦ 结点 u 通过反祖边到达结点 v，或者通过横叉边到达结点 v 并且满 足 low 定义中 v 的性质 low[u] = min(low[u], dfn[v]) hzwer,miskcoo 图论及其应用 北京大学, 清华大学 53 / 75
  • 146.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75
  • 147.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 如何更新 low？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75
  • 148.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 在 tarjan 算法进行 DFS 的过程中，每离开一个结点，我们就判断一下 low 是否小于 dfn，如果是，那么着个结点可以到达它先前的结点再通过那 个结点回到它，肯定不是强连通分量的根。如果 dfn 和 low 相等，那么就 不断退栈直到当前结点为止，这些结点就属于一个强连通分量。 如何更新 low？ 关键就在于第二种情况，当通过反祖边或者横叉边走到一个结点的时 候，只需要判断这个结点是否在栈中，如果在就用它的 low 值更新当前节 点的 low 值，否则就不更新。因为如果不在栈中这个结点就已经确定在某个 强连通分量中了，不可能回到 u。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 54 / 75
  • 149.图论基础 图论算法 例题 有向图的强连通分量 Tarjan 算法 具体参见我的 hzwer,miskcoo 。 图论及其应用 北京大学, 清华大学 55 / 75
  • 150.图论基础 图论算法 无向图的双连通分量、割点与桥 1 图论基础 2 图论算法 拓扑排序 生成树 最近公共祖先和倍增算法 单源最短路 所有顶点间的最段路 有向图的强连通分量 无向图的双连通分量、割点与桥 3 例题 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 56 / 75
  • 151.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 在图论中，如果在一个无向连通图中删除一个结点及与它相关的边之 后，该图被分成两个或者更多的连通分量，那么这个点就被称为割点（cut vertex），也被称为关节点（articulation vertex）。如果一个无向连通图没 有割点，那么就称该图为点双连通图。无向图的极大点双连通子图被称为点 双连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 57 / 75
  • 152.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 在图论中，如果在一个无向连通图中删除一个结点及与它相关的边之 后，该图被分成两个或者更多的连通分量，那么这个点就被称为割点（cut vertex），也被称为关节点（articulation vertex）。如果一个无向连通图没 有割点，那么就称该图为点双连通图。无向图的极大点双连通子图被称为点 双连通分量。 如果在一个无向连通图中删除一条边后，该图被分成两个或者更多的连 通分量，那么这条边就被称为割边（cut edge），也被称为桥（bridge）。如 果一个无向连通图没有割边，那么就称该图为边双连通图。无向图的极大边 双连通子图被称为边双连通分量。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 57 / 75
  • 153.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75
  • 154.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75
  • 155.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 如果结点 u 不是搜索树的根，那么当存在 v 是 u 的儿子并且并且满足 dfn[u] ≤ low[v]，那么结点 u 也是割点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75
  • 156.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 无向图的双连通分量、割点与桥 求解割点的方法和有向图的 tarjan 算法类似。我们保留 dfn 的定义不 变，由于无向图在 DFS 的过程中不会出现横叉边，low 的定义改变为从子 树中经过反祖边能够到达的时间戳最小的结点。 如果结点 u 是整棵搜索树的根，那么它是割点当且仅当 u 有两个及以 上的儿子。 如果结点 u 不是搜索树的根，那么当存在 v 是 u 的儿子并且并且满足 dfn[u] ≤ low[v]，那么结点 u 也是割点。 至于割边，上面不等式改成小于号即可。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 58 / 75
  • 157.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75
  • 158.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75
  • 159.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75
  • 160.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 选择度数为 m-(n-2) 的非割点结点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75
  • 161.图论基础 图论算法 例题 无向图的双连通分量、割点与桥 例题 1 UOJ27 给出一个有 n 个结点，m 条边的无向图，问有哪些结点满足：删去该 点后原图变为一棵树。 其中 0 < n, m < 105。 树是 n 个点 n-1 条边的无向连通图 删去该点原图连通且边变为 n-2 条 选择度数为 m-(n-2) 的非割点结点 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 59 / 75
  • 162.图论基础 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 60 / 75
  • 163.图论基础 例题. 混合图 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 61 / 75
  • 164.图论基础 图论算法 例题 例题. 混合图 混合图 你有一个混合图，它有 n 个顶点，m 条边，其中 a 条是有向边，b 条 是无向边。现在要求为这 b 条无向边确定一个方向，使得最后的有向图上不 存在环。 其中 1 ≤ n, a, b ≤ 105, m = a + b。不用考虑无解的情况。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 62 / 75
  • 165.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75
  • 166.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75
  • 167.图论基础 图论算法 例题 例题. 混合图 混合图 既然要求最后的有向图没有环，也就是要求最后是个 DAG！ DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。 先把无向边忽略，对图进行拓扑排序，最后无向边的方向就是拓扑序小 的连向拓扑序大的。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 63 / 75
  • 168.图论基础 例题. 灾后重建 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 64 / 75
  • 169.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对 公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公 路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通 车，只能到达重建完成的村庄。 给出 B 地区的村庄数 n，村庄编号从 1 到 n，和所有 m 条公路的长度， 公路是双向的。并给出第 i 个村庄重建完成的时间 t[i]，你可以认为是同时 开始重建并在第 t[i] 天重建完成，并且在当天即可通车。若 t[i] 为 0 则说明 地震未对此地区造成损坏，一开始就可以通车。之后有 Q 个询问 (x, y, t)， 对于每个询问你要回答在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多 少。如果无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村 庄，或者村庄 x 或村庄 y 在第 t 天仍未重建完成，则需要返回-1。 数据保证 t[1]≤t[2]≤ · · · ≤t[n]。并且 0 < n ≤ 200, 0 < Q ≤ 50000。 Source：福建 NOIP 夏令营 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 65 / 75
  • 170.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75
  • 171.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 最短路只能经过前 i 个村庄。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75
  • 172.图论基础 图论算法 例题 例题. 灾后重建 灾后重建 在第 i 个村庄重建完成时，前面村庄都重建完成了，后面的村庄都没有 重建完成。 最短路只能经过前 i 个村庄。 Floyd！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 66 / 75
  • 173.图论基础 例题. 肮脏的道路 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 67 / 75
  • 174.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 有一个 n 个结点 m 条边的无向图，边有权值。 从一个结点 s 到另一个结点 t 的一条路径的肮脏值定义为路径上权值最 大的那条边的权值。 要求计算出从 s 到 t 的所有路径中肮脏值最小的那条路径的肮脏值。 其中 1 ≤ n ≤ 10000, 1 ≤ m ≤ 20000。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 68 / 75
  • 175.图论基础 图论算法 例题. 肮脏的道路 肮脏的道路 二分？ hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 69 / 75
  • 176.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 二分？ 类似 Kruskal 算法直接判断连通。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 69 / 75
  • 177.图论基础 图论算法 例题 例题. 肮脏的道路 肮脏的道路 二分？ 类似 Kruskal 算法直接判断连通。 事实上，这样的路径叫做最小 路。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 69 / 75
  • 178.图论基础 例题. Candies 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 70 / 75
  • 179.图论基础 图论算法 例题 例题. Candies Candies 有 n 个人分糖果，现在有 m 个限制，比如说某一个人得到的糖果不能 比另一个人少 k 个以上。 请你求出小 A 比小 B 最多能多得到多少个糖果。 其中 1 ≤ n ≤ 30000, 1 ≤ m ≤ 150000。 Source：POJ 3159. Candies hzwer,miskcoo 图论及其应用 北京大学, 清华大学 71 / 75
  • 180.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75
  • 181.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k 将每个人看成一个点，比如上面这个限制就从 B 向 A 连接一条长度为 k 的边。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75
  • 182.图论基础 图论算法 例题 例题. Candies Candies 比如小 B 得到的糖果不能比小 A 少 k 个以上，那么 A−B≤k 将每个人看成一个点，比如上面这个限制就从 B 向 A 连接一条长度为 k 的边。 最短路 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 72 / 75
  • 183.图论基础 例题. 和平委员会 图论算法 1 图论基础 2 图论算法 3 例题 例题. 混合图 例题. 灾后重建 例题. 肮脏的道路 例题. Candies 例题. 和平委员会 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 73 / 75
  • 184.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 某国有 n 个党派，每个党派在议会中恰有 2 个代表。有 m 对代表之间 会有矛盾存在。 现在要成立和平委员会，该会满足： • 每个党派在和平委员会中有且只有一个代表。 • 如果某两个代表存在矛盾，则他们不能都属于委员会。 判断是否能够成立这个委员会。如果能，给出方案。 其中 1 ≤ n ≤ 8000, 1 ≤ m ≤ 20000。 Source：Poi 0106 Peaceful Commission hzwer,miskcoo 图论及其应用 北京大学, 清华大学 74 / 75
  • 185.图论基础 图论算法 例题. 和平委员会 和平委员会 将每个代表看成一个点。 hzwer,miskcoo 图论及其应用 例题 北京大学, 清华大学 75 / 75
  • 186.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75
  • 187.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 若一个党派的人在一个环内无解！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75
  • 188.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 将每个代表看成一个点。 如果代表 A 在委员会，代表 B 必须在委员会则连一条有向边从 A 到 B。 若一个党派的人在一个环内无解！ 缩环！ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 75 / 75
  • 189.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 190.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 191.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 192.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 193.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 194.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 195.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 按照拓扑序来找点。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75
  • 196.图论基础 图论算法 例题 例题. 和平委员会 和平委员会 剩下的情况就是有解吗？是的话如何给出方案？ 图有什么性质？ 边是对称的 如果一个点 A 在，它对应的另一个点 A′ 就不能在。 所有 A′ 的祖先也都不能在。 将边反向 按照拓扑序来找点。 这个问题实际上被称为 2-SAT 问题。 hzwer,miskcoo 图论及其应用 北京大学, 清华大学 76 / 75