图论学习笔记

TUIFEI_oier · 2020-08-01 11:28:57 · 个人记录

0721 图论 学习笔记

By CSYZ1914

前言

终于是迎来了高中的第一个暑假（虽然只有 6 天（当然比起没有来说还是要好得多））。
从现在开始就是 7 天的课程培训，每一章大概都会写一篇学习笔记加深自己理解。
大概就这样了（虽然估计会咕）。

Part 1 最短路&生成树

大部分人第一次接触图论估计都是这两类算法，这也确实是图论中最基础的两种常用算法。但尽管如此，这两种算法也有着广泛的变形空间。

最短路算法

常用的最短路算法：

1. Dijkstra
2. Spfa
3. Floyd

一般来说也就是以这三种算法为主，其中 Floyd 因为某些原因在一般的图论题中并不常用（复杂度"略"高），所以主要还算前两种算法用处较大。
接下来通过一些例题记录它们的用法和变形：

Pro A (CF 575G)

题意：给定一个 n 个点 m 条边的带权无向图，求 1 到 n 的最短路径，路径长度定义为路径所包含的边的权值按顺序写成一个十进制数。

首先，我们可以发现这个题就是求一个单源最短路可以解决的问题，但是这里有一个问题——路径的长度定义是有区别的。
这个时候，我们就可以考虑一种算法，使得我们可以重新规定每条边的边权，使它满足贪心的性质，就可以用高效的 Dijkstra 算法来解决这道题了。
这样一来，我们就要找一种使得新的边权可以重新满足 Dijkstra 贪心性质的方法。

考虑现在取出一个点进行更新操作，如果一个节点可以被取出更新其他节点，一定要保证其他节点不会又更新到它，所以我们可以从 n 号节点开始跑最短路，则每次取出到 n 的路径长度最小的节点来更新其他点是肯定合法的。那么只要考虑边权的定义问题。我们考虑这样一种边权的定义方式：用当前节点在所有已锁定的节点中的排名（可相等） rk\cdot10+w 来作为当前边权，这样就可以保证边权是可以正确比较的了。（相对大小）
复杂度即为 O(nlogn)。

生成树算法

常用的生成树包括最小生成树和次小生成树，所以以这两种为主。
常用的最小生成树算法：

1. Kruscal
2. Prim
3. Sollin

其中 Sollin 算法区别于另外两种算法，可以实现不保存边权而在线求值维护，所以通常会和一些其他的算法结合起来（说人话就是空间复杂度可以低于 O(min(m,n^2))）。
然后就是一些经典的应用了。

Pro B (CF 723F)

题意：给定一个 n 个点 m 条边的无向图，求一个原图生成树满足两个特殊点 S,T 在生成树中的度数分别不超过 d_S,d_T。

这道题的做法算是比较巧妙的。
首先把所有和 S,T 有关的边给断掉，然后就会得到一个个的连通块。
然后，如果一个块只和 S,T 中的一个有边，那是绝对要连上的。
之后对于和两者都连边的，贪心地每次让剩余度数多的那一个去连，记得要保证 S,T 之间的连通。
具体的实现就可以通过给一些无关 S,T 的边边权设为 0 ，绝对要连上的边边权设为 1 ，然后按 d_S,d_T 大小贪心设置连边优先级，最后跑 Kruscal 即可。
复杂度 O(mlogm)。

Pro C (CF 1023F)

给定 n 个点 m 条边的无向图，边有黑边也有白边，其中 k 条是白边。黑边的权值确定而白边的权值可以随意指定，求一种方案使得图的最小生成树中包含所有白边且白边权值和最大。

首先，假设所有白边边权为 -\infty，则所有白边一定会出现在最小生成树中。
接下来，考虑不断增大一条白边的权值，但是要保证它不会从最小生成树中淘汰，也就是说它不能超过若干树边和一条非树边组成的环上的最大值，类似于次小生成树的求解过程中的辅助数组，然后所有边顶上界即可（因为它们互不影响）。

Part 2 网络流

从这里开始就是一些图论中的经典模型以及它们在 oi 中的应用了。大多数情况下你可以把网络流看成是一种可以解决某些特定问题的工具，也因此学习网络流本质上是学习如何建图来用好这个“工具”。

基本算法

1. 二分图匹配算法：匈牙利、KM（不常用）
2. 最大流算法：EK,Dinic（最常用）
3. 费用流算法：MCMF,zkw费用流（最常用）

这就是网络流及其衍生算法中的主要内容了。 OI 中的网络流题型基本上只会用到这些算法。

模型构建

这里开始就是网络流的重头戏了，建模方式才是这玩意儿的核心。
接下来介绍几种常用的模型：

1. 最大流模型
   A. 最大值求解类：按照题意所述建出图，最后的最大流就是所求答案。
   B. 方案判定类：利用最大流的流量约束来实现某些限制问题，然后判断是否满流来确定方案是否合法可行。
   C. 方案构建类：通过网络流的流量分配机制来实现方案的生成。
2. 最小割模型
   A. 方案生成类：经典的最大权闭合子图型问题，割边代表不去选择，一条 S-T 的流意味着一个操作或途径。 B. 最小损失类：最大收益=总收益-最小损失。所以可以考虑用最小割的思路思考问题，割边代表接受这条边带来的损失。
   C. 额外收益型：先不考虑固定可得的收益，转而考虑能额外得到的收益并最大化这个值，从而割边代表着放弃这个额外收益。
3. 最小费用模型：
   A. 最小代价型：直接按题意建出图来，然后通过最小费用最大流来实现在满足某些条件的同时最小化费用。
   B. 额外费用型：先确定出固定的花费，然后最小化额外的花费，是否割边意味着是否接受这个额外损失。

例题集合

Pro A (CF 512C)

题意：给定 n 个整数 a_1,...a_n ，要求把这 n 个整数排列成若干个环，使得每个环的大小 \ge3 且相邻两个数之和为质数，求任意一个合法方案。

分析题意可得，相邻两数之和必然是奇数，也就是相邻两数的奇偶性不同。
这启示我们建一个二分图，奇数一边，偶数一边，然后就是比较好解决的了。

Pro B (CF 802C)

题意：你有一个最多装 k 本书的书架。从第 1 天到第 n 天，你每天都要求看一本书，第 i 天要看的书为 a_i。要看的书可以是当天买，也可以是之前就放在书架里。每天看完书后你可以决定书架里哪些书需要丢掉（当天买的也算），第 i 本书价格为 c_i ，求最小花费。

首先，我们考虑用最小化损失的角度来考虑，也就是最大化可以节省的钱。
假设每天书都是要看就买，看完就丢（不使用书架），那么总费用就是 \sum_{i=1}^nc_{a_i}。
考虑最大化可以节省下来的钱，如果第 i,j 天要看同一本书，那么可以考虑让这本书从第 i 天一直留到第 j 天并占用书架的一个位置，这样就转化成区间 K 覆盖了，细节参见题解。

Pro C (CF 786E)

给定一棵 n 个点的树，同时给出树上的 m 条路径，每次花费 1 费用来标记路径或者一条树边，要求每条路径要不自己被标记，要不它包含的所有边都被标记，求最小代价以及其对应的任意一组方案。

首先，不难发现这是一个经典的二分图最大权闭合子图问题，把一条路径看成一个点，一条边看成一个点，所有路径向包含的边连边即可。
但是这个复杂度有点不对，或者问题很大。这时用线段树或者倍增优化建图即可。（此题还有一个有意思的结论，可以让线段树优化建图的版本跑得快十几倍。）

Part 3 缩点&连通块

这就是 Tarjan 全家桶的地盘了，很少有缩点题是不用 Tarjan 算法来解决的。（所以 Tarjan 全家桶还是香啊）

Tarjan全家桶

1. 强连通分量
2. 割点、点双
3. 桥、边双
4. 离线 LCA（额外内容）

   例题集合

   Pro A (CF 555E)

   给定 n 个点 m 条边的无向图，判断是否可以给每条边确定方向使得满足 k 条形如 s_i 可以到达 t_i 的限制。

   tips::1\le n,m,k\le10^5

首先，定向后一个强连通分量内点都是可以相互到达的，而在无向图上一个边双恰好可以定向成一个强连通分量，所以我们可以先把每个边双缩成一个点，这时恰好得到了一颗树。
然后就只要考虑一棵树的情况了，树上差分即可。

Pro B (???)

给定 n 个点 m 条边的有向图，求有多少个点可以到达其他所有点。

直接强连通分量缩点，之后只能是一个树形图才存在唯一解。

Summary

这里只总结了一些本人觉得比较有代表意义的算法及题目，当然图论的各种技巧也不止步于此，还是需要不断积累。