Java教程

图论问题复习总结

本文主要是介绍图论问题复习总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

图论问题复习总结

图论梗概:大类上,图的概念(重心,直径,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 就说明守卫合格了。

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

这篇关于图论问题复习总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!