图论问题复习总结

图论梗概：大类上，图的概念(重心，直径，LCA等)，最短路，最小生成树，图的连通性(圆方树等)，二分图(图的匹配)，网络流；杂项上，2-SAT，prufer序列，欧拉回路，矩阵树定理，拆点/边，哈密顿路，树hash，建虚树等。特殊的图：仙人掌，基环树。

图论基础

普及组-提高的知识点，涉及广泛，几道例题如下(口胡的内容都是题目)。

• 差分约束

  ​ lgP3275 糖果

  ​ 一般来讲，给出关系 a ≤ b a\le b a≤b,那么 a → b a\to b a→b 连一个边权为0的边，如果是 a < b a<b a<b，那么 a → b a\to b a→b 连一条边权为1的边，然后类似拓扑的，建超级源点到所有入度为0的点，然后跑最长路,每个点的 d i s dis dis 就是它最小的值。如果出现了环，那就自相矛盾而产生无解。

• kruskal的应用

  ​ CF723F st-Spanning Tree

  ​ 除了一般的最小生成树，kruskal还能很好的处理一些自定义权的问题。

  ​ 要求S，T的度数不能超过ds,dt来生成树，那么可以定义一个优先级，针对连着S和T的边来定义优先级1，2(ds大那么连着S的就是1) 来进行kruskal，其它的先随便生成一颗树，然后针对一个生成森林再考虑这些边的连接，如果ds==dt的话，就要跑两次这个过程，一次让S的优先级为1，一次让T的优先级为1，这样的贪心正确性大概可以通过ds大的时候一个森林连S一定不会更劣这样来说。

• 广义/重定义/分层图

  ​ CF575G Run for beer

  ​ 分层图，一般来说是点之间有拓扑的关系，然后需要分层来处理，这个时候还可以加上一些最短路的重定义。

  ​ 求 1 → n 1\to n 1→n 中把路径边权接成十进制需要的最短路径，这个时候是优先考虑长度再考虑字典序，先bfs预处理一个点到 n n n 经过的边数，然后从s出发，每次找这个dis最小的一些点，再在这些点里选择此次字典序最小的一些点，然后再考虑这些点继续向下bfs下去，如果有前导0的话就多考虑一个前导全是0的点，然后从这些点开始就好,还要考虑前导的边数，所以还要记录一个dis_s表示从s走来的边，对于数的大小相等的，比较从s到t的边数。

匹配与网络流

匹配

• 图的匹配

  • maximal matching：不能再加边的匹配，不一定是最大匹配
  • 最大匹配：边数最多的匹配
  • 完美匹配：所有点都在的匹配
  • 近似完美匹配：图的点数为奇数，刚好只有一个点不在匹配中，换言之如果没有这个点就是完美匹配

• 二分图的匹配

  • 二分图的完美匹配：对于小的那一半，使得所有点都属于匹配
  • 霍尔定理：对于小的那一半，如果任选K个点，都有至少K个点和它们相邻(有边)，那么一定有完美匹配。或者说在图G中存在一组没有公共点的边使得一端的端点恰好是二分图的一半，它的充要条件是对于小的那一半，如果任选K个点，都有至少K个点和它们相邻(有边)。附：正则二分图(每个点度数相同)一定有完美匹配。

网络流

• 最大流解决二分图最大匹配

  • CF510E Fox And Dinner （二分图找环）

  ​ 考虑将奇数和偶数分成二分图，然后对于和为质数的连边，由于最后要形成一个环，所以对于每个点向源汇点的边的容量为2，而匹配的容量只有1，然后跑最大匹配，最大流是n才能保证可以形成若干个质数相邻环，对于输出方案，对于残留网络的边为0的，可以知道若产生从左到右的匹配，那么正向边为0，否则反向边为0，标记一下已经遍历过的点，每次搞个vector存下这个环即可。

  • [Bytedance Camp 2019]Deep in the Ocean（二分图找环）

  n个点m条边的无向图，满足每个点度数相等且是偶数。在里面找出一个边的子集，满足每个点的度数是2。
  n , m ≤ 1 0 5 n,m\leq 10^5 n,m≤105

  ​ 首先这是一个正则图，所以把每个点复制一份然后变成二分图一定存在完美匹配，然后就和上边这道抽环类似，但是这里有一个问题就是无向图(u,v)需要建两次边，所以可能一个点会被走两次，所以考虑把(u,v)只保留一个单向边，由于每个点的度数又都是偶数，所以存在欧拉回路，而欧拉回路一定也是一个正则图（入度==出度），那么保留欧拉回路上的有向边再跑二分图匹配即可，和上道题的匹配方式一样。

• 费用流

  • CF802C Heidi and Library (hard)(区间k覆盖)

    ​ 每本书买卖存分开考虑，所以每个点拆成入点和出点，以表示购入和卖出，考虑每本书买来费用是 c [ a [ i ] ] c[a[i]] c[a[i]] ，连边 s → i s\to i s→i,容量1，费用 c [ a [ i ] ] c[a[i]] c[a[i]]，为了使得一段区间内能够保留这本书，连边 i → i + 1 i\to i+1 i→i+1容量 K − 1 K-1 K−1,费用0，表示可以传递最多 K − 1 K-1 K−1本书到下个位置，考虑扔掉的时机，保留到下次买这本书时即可让下次不花钱，可以连边 i − 1 → l a s t [ a [ i ] ] + n i-1\to last[a[i]]+n i−1→last[a[i]]+n ，容量是1，费用是 − c [ a [ i ] ] -c[a[i]] −c[a[i]]，也就是回到上次的扔书点，将这次的费用退回，这里一定要是 i − 1 → l a s t [ a [ i ] ] + n i-1\to last[a[i]]+n i−1→last[a[i]]+n，来表示一个这天才扔掉这本书的回收，然后再从这个先前需要扔掉的位置考虑它的流；剩下的， i → i + n i\to i+n i→i+n,建边容量1，费用0，表示当天扔掉， i + n → t i+n \to t i+n→t 容量1，费用0，表示要么扔，要么卖(第二类边回退的过程会带来的卖的费用)。

各种不常见图论算法

​ 包括各种神仙构造，最小树形图，k短路，平面图算法，支配树，一般图匹配，拟阵交，保序回归等。(保序回归(2020)和支配树(2021)都是省选里考过的，其中支配树这个让我省选大惊(基本抱玲)…)
​ 这部分除了最小树形图和k短路是学习过的，其它都没有。

杂题

各种知识点,虽然题解较短,但写起来还是蛮长蛮细节的。

• P2341 受欢迎的牛(tarjan/强连通分量)

  ​ 考虑对于 x → y x\to y x→y 表示y喜欢x，若存在答案则是入度为0的强连通分量的siz，存在答案应当是只存在一个入度为0的强连通分量且它的siz为n(二者其实互为充要)，要注意此图不是树，求siz这种方法需要判断一下一个点的siz是否被记录过。

• 机棚障碍

  综合应用题——二分+缩点(另类)+克鲁斯卡尔重构树

  1. 求每个格子能放下的最大正方形记录边长mx ，二分答案即可。
  2. 把mx相等的联通块缩成一个点
  3. 跑克鲁斯卡尔重构树，小根堆
  4. 求每两点的lca,点权即是路径上边权最小值 ,记得除了新建的点，原点的权值是连通块的mx。

• CF555E Case of Computer Network

  ​ 一个边双可以定向成一个强连通分量，那么可以缩点边双后忽略强联通，然后只考虑树边，可以树上差分记录向下传递的需求和向上传递的需求，一个s1和一个s2，如果一个点既要向下传递又要向上传递，那么需求是冲突的，就无法定向，否则可以定向，另外如果两点不在同一颗树上也显然不能定向。

  错误注意（调了一个多小时）:缩完点之后再连边一定要注意一个顺序，要么根据新的编号大小(c[x]<c[y]时连边)，要么根据一些位置关系之类的，不然会连重边或者说连错(用并查集也可能出错)，上一道题也是这样(无意间避免了)。

• AGC044B Joker(精妙DFS——费脑题)

  ​ 设 d [ i ] [ j ] d[i][j] d[i][j]为点 ( i , j ) (i,j) (i,j)能够出来的最少路过的人，那么一开始 ∑ d [ i ] [ j ] \sum d[i][j] ∑d[i][j]是 n 3 n^3 n3级别的，这意味着我们精准的修改一定能够让它在 O ( n 3 ) O(n^3) O(n3)结束，注意到对于一条最短的路径一定是递减的，所以对于一次修改，修改过 d [ x ] [ y ] − − d[x][y]-- d[x][y]−−后(注意这里因为递归先修改了)，只需要 d [ n x ] [ n y ] = d [ x ] [ y ] + 2 d[nx][ny]=d[x][y]+2 d[nx][ny]=d[x][y]+2就可以让 d [ n x ] [ n y ] d[nx][ny] d[nx][ny]得到修改,不过还要考虑 ( n x , n y ) (nx,ny) (nx,ny) 是否被使用过，如果被使用过的话，这个位置就要 d [ n x ] [ n y ] = d [ x ] [ y ] + 1 d[nx][ny]=d[x][y]+1 d[nx][ny]=d[x][y]+1 才行（也就是说原来(x,y)的代价是等于(nx,ny)的,所以路过这里”如履平地“,用于更新其它点）。简单点，只要一句 d [ n x ] [ n y ] + v i s [ n x ] [ n y ] = d [ x ] [ y ] + 2 d[nx][ny]+vis[nx][ny]=d[x][y]+2 d[nx][ny]+vis[nx][ny]=d[x][y]+2 即可(即可继续递归让它–)。

• 旅行者(二进制分组)

  ​ 感动，终于有一道以前做过的题。用的方法是二进制分组，由于求的是关键点之间两两的最短路，可以考虑分组logn次，根据第i位是0还是1来分组，然后正常建图的同时让S连0组T连1组边权为0，接着跑最短路，dis[T]最短的一次就是最优的答案，原理是最优匹配 ( x , y ) (x,y) (x,y)一定有一次不在一组。因为这道题图是有向图，所以还得再来一次S连1组T连0组。二进制分组大概就是要使得最优匹配能够在一次分组中出现。

• CF1023F Mobile Phone Network(”模拟“最小生成树)

  ​ 先把边排序，要把所有白边加上去，一开始赋值为0，黑边权值不变的跑一个最小生成树，然后考虑黑边对于白边的覆盖，一个黑边覆盖一段白边的话(跨过 u → v u\to v u→v，而 u → v u\to v u→v之间的白边权值还没有被更新)，那么对于还没有被更小的黑边覆盖更新的白边，更新为它的权值，先考虑怎样更新，对于一个 u → v u\to v u→v，选择较浅的那个暴力跳dep，对于路径上的所有没有赋值的白边都赋值为这个黑边的权值(边权事先存到点上)，直接在ans里累计这些边权即可，当然不能每次都暴力跳，所以考虑用并查集来跳跃已经处理过的边，也就是更新一下点的fa,每次跳的时候合并x到fa[x]的并查集上，然后跳到根的fa上去，这样可跳次数会越来越少，总复杂度 O ( n l o g n + n α ( n ) ) O(nlogn+n\alpha(n)) O(nlogn+nα(n))

• ALT(最小割+线段树优化建图)

  ​ 最大流=最小割=最小点权覆盖集=sum-最大点权独立集。网络流嘛。。就是考建图。

  ​ 连接 s → i s\to i s→i 容量为1，连接 i → [ l , r ] i\to[l,r] i→[l,r] 容量为∞，连接 [ l , r ] → t [l,r]\to t [l,r]→t 容量为1。然后最小割就是答案。模拟一下,就是割掉 s → i s\to i s→i 表示给了居民宠物，割掉 [ l , r ] → t [l,r]\to t [l,r]→t 就是给了守卫宠物，而 s s s 流不到 t t t 就说明守卫合格了。

其它还有好多题，然而我太菜了搞不了这么多，就只有以上了，退役前不知道还有没有時間再搞搞剩下的。