LCA图论_专题_LCA
JueFan 一只绝帆

LCA 图论

点/边覆盖 点/边独立集

我们常说的匹配就是边独立集。

在一般图上点覆盖 ≥\ge 边独立集,边覆盖 ≥\ge 点独立集,这是因为一个点/边不可能覆盖独立集里的多个边/点,二分图上二者可以取等。

注意边覆盖的定义需要图中无孤点,否则无法覆盖。

点独立集的补集总是点覆盖,反之亦然,边独立集的补集总是边覆盖,反之亦然,这是根据定义天然满足的。

如何证明二分图上最大匹配、最小点覆盖、最大独立集、最小边覆盖上的数量关系?我们需要一个更强的分析结构。

最大团

最大团总是补图的最大独立集,而二分图最大独立集是好做的,所以如果是两个团为基底的图,两个团中间连一些边,对这个图求最大团,可以转化为求补图(是一个二分图)的最大独立集。

P2423 [HEOI2012] 朋友圈

在很久很久以前,曾经有两个国家和睦相处,无忧无虑的生活着.

一年一度的评比大会开始了,作为和平的两国,一个朋友圈数量最多的永远都是最值得他人的尊敬,所以现在就是需要你求朋友圈的最大数目.两个国家看成是 AB 两国,现在是两个国家的描述:

  • A 国:每个人都有一个友善值,当两个 A 国人的友善值 a,ba,b,如果 (axorb) mod 2=1(a\mathbin{\mathrm{xor}} b) \bmod 2=1,那么这两个人都是朋友,否则不是;
  • B 国:每个人都有一个友善值,当两个 B 国人的友善值 a,ba,b,如果 (axorb) mod 2=0(a\mathbin{\mathrm{xor}} b) \bmod 2=0 或者 (aorb)(a\mathbin{\mathrm{or}} b) 化成二进制有奇数个 11,那么两个人是朋友,否则不是朋友.

A、B 两国之间的人也有可能是朋友,数据中将会给出 A、B 之间「朋友」的情况.

对于朋友的定义,关系是是双向的.

在 AB 两国,朋友圈的定义:一个朋友圈集合 SS,满足 S⊂A∪BS \subset A \cup B,对于所有的 i,j∈Si,j \in S,ii 和 jj 是朋友.

求最大朋友圈。

T≤6T\le 6。

  • 第一类:1≤A≤200,1≤B≤2001 \le A \le 200, 1 \le B \le 200.
  • 第二类:1≤A≤10,1≤B≤30001 \le A \le 10, 1 \le B \le 3000.

求的是这个图的最大团。

AA 图是个二分图,最大团最多是 22,所以这个东西是最后的细节工作,先不管。

BB 图是基于两个团的图加了一些边,根据上面的 trick,最大团等于补图最大独立集,转成二分图最大匹配。

对于 AA 图,我们枚举里面点的贡献,00 不用管,11 就枚举每个点,然后保留与这个点联通的 BB 图点跑最大团,22 就是枚举一条边。

古老题的复杂度不是很对,不过时间戳优化的匈牙利不需要每次重新建图,跑的很快。

二分图匹配的匈牙利树结构

对于一个已经求完最大匹配的二分图,我们再次对其跑匈牙利算法,对每个非匹配点跑匈牙利算法,并使用 dfs\rm dfs 的剪枝,我们几乎会得到一棵 dfs\rm dfs 树。

点可以分为(匹配点,非匹配点)、(奇层点,偶层点)、(在其他非匹配点搜过,没搜过),边可以分为(匹配边,非匹配边)。

对其分析一下:

  • 奇数层到偶数层是未匹配边,一个点可能有多个儿子,偶数层到奇数层是匹配边,一个点只有一个儿子。
  • 奇数层连未搜过的匹配点:儿子。
  • 奇数层连搜过的匹配点:返祖边/横叉边。
  • (不存在)奇数层连非匹配点:非匹配点也是另一棵树的根,这两棵树共用了这条到根的链,不可能发生因为此时存在一条 增广路。
  • 偶数层匹配的另一端:儿子。
  • 偶数层连向非匹配点:另一棵树的根,这两棵树共用了这个点的子树。
  • 偶数层连(并非匹配的另一端)的匹配点:要么满足 存在另一棵树横叉边到这颗树,要么是一个无法搜到的位置,若是后者,我们称其为 完美匹配结构,这个结构中每个点都是匹配点,很多题目中完美匹配的处理是平凡的,所以这个结构通常并不关心。

分析一下,我们至少可以把所有树根拎到上面,两棵树只会共用子树而不会共用链,所以我们。

其有如下性质:

  • 根是未匹配点,奇数层到偶数层是未匹配边,一个点可能有多个儿子,偶数层到奇数层是匹配边,一个点只有一个儿子(根的深度是 11)。
  • 树上有返祖边、跨两棵树的横叉边 和 完美匹配结构 三种特殊结构。
  • 叶子一定是奇数层的匹配点,否则该图存在增广路。
  • 由于是二分图不能有奇环,返祖边一定是奇数层连到偶数层,跨树的横叉边由于你都把根拎起来了,也一定是奇数层连到偶数层。
  • 每个联通块的奇/偶层划分一定是原图的左/右(右/左)划分,构成二分图。

我们用这个东西来分析一下前文的问题,全都归约到匹配上:

如何证明二分图上最大匹配、最小点覆盖、最大独立集、最小边覆盖上的数量关系?

最小点覆盖:每条匹配边至少要选一个点,我们证明存在一种方案即可,对于树结构我们选所有偶数层的点(点数等于匹配边数),观察上面的所有边都是连接奇数层和偶数层的,对于完美匹配结构我们全选左部点/右部点即可。

最大独立集:虽然就是最小点覆盖取补集,但我们也可以用同样方式分析:每个匹配至多选一个点,我们尽量全选未匹配点,树结构只需选奇数层的点即可,每个匹配都选了一个点,每个未匹配点也都选了,性质中指出没有奇数层之间的边,完美匹配结构全选左部点即可。

最小边覆盖:考虑一条一条加入边覆盖的过程,覆盖的点数只会 +1+1 和 +2+2,边数就是 n−(+2)n-(+2) 的次数 。

考虑 +2+2 的边一定构成匹配,我们要最大化这个数量,那我们就取最大匹配中的边,每个未匹配点再配一个 +1+1 即可。

P7816 「Stoi2029」以父之名

给定一个 nn 个点 mm 条边的无向图,边权均为 11 或 22。保证每个点所相连的边权值之和均为奇数。你需要将这些边定向,使每个点的入边权值和与出边权值和之差的绝对值恰为 11。保证有解。输出任意一种方案。

第一行两个正整数:n,mn,m,表示有 nn 个罪人和 mm 条罪的联系。

接下来 mm 行,第 i+1i+1 行为三个正整数:ui,vi,wiu_i,v_i,w_i,表示第 ii 条联系连接 uiu_i 与 viv_i 且值为 wiw_i。

对于 100%100\% 的数据,1≤ui,vi≤n≤1061 \le u_i,v_i \le n \le 10^6,1≤m≤3×1061 \le m \le 3 \times 10^6,wi∈{1,2}w_i \in \{1,2\}。

两种理解方式:

  1. 欧拉回路算法是可以进行配对的,你可以限定从谁入导向从谁出,所以对于有偶数个 22 的人,你把 22 两两配对,11 两两配对,剩一个 11 与虚边配对,对于有奇数个 22 的人,我们直接两两配对,然后剩一个 11 与 22 配对,跑欧拉回路即可。

  2. 本题的关键并不是看到绝对值是 11 马上每个点从虚点连一下,连了就爆了,此时一个初步的想法是先定 22 再定 11,如果这个点有奇数个 22 最后会剩下一个 22,那么我们要求它 11 的配对中剩余点的方向和 22 的方向相反,这个要求很强,两个图做不了。

    只需建一个分层图,第一层是 22 边第二层是 11 边,如果 22 边度数是偶数,就把第二层的点连向虚点,否则就连接两层的两个点(这样限制了两边的剩余方向不同),直接跑欧拉回路即可。

P9150 邮箱题

有一张 nn 个点和 mm 条边构成的有向图。每个点内都有一把另一个点的钥匙,ii 号点内有 kik_i 号点的钥匙。你能进入一个点当且仅当你有该点的钥匙。保证 kik_i 构成排列。

只要进入了一个点,就获得了这个点内有的钥匙。一旦获得钥匙就不会被消耗。

现在你拿到了 ii 号点的钥匙并到了 ii 号点。你需要对每个 ii 求出:

  1. 有多少点能被你到达。
  2. 有多少点能被你到达并返回起点 ii。

请注意:给出的边均是有向边!

对于 100%100\% 的数据,满足 n≥3n \ge 3,m≥0m\ge 0,∑n≤1.5×106\sum n\le 1.5\times{10}^6,∑m≤3×106\sum m\le 3\times{10}^6,1≤T≤2×1041 \le T\le 2\times{10}^4,1≤x,y≤n1 \le x, y \le n,保证图中不含重边或自环。

性质

首先可达关系是闭包,如果 i→ji\to j,那么 jj 能到的 ii 一定能到,理由就是到达 jj 时钥匙只会更多。

返回关系也有很强的性质,如果 ii 能返回 jj,那么 (j,i)(j,i) 的这些人可以 ii 先返回 jj 再从 jj 走到这些点。

其次我们每时每刻还没开启的持在手上的钥匙只有一把,所以我们实质上是在排列的环上跑。

暴力

我们已经有了一个高复杂度 poly\text{poly} 做法,即每次判断能不能在环上多走一步时,都跑一遍连通性 ii 能不能通过 [s,i][s,i] 的人到达 nxtinxt_i,这是三方的。

接着思考,由于我们需要判断“ ii 能不能通过 [s,i][s,i] 的人到达 nxtinxt_i”,假设这个过程中跳到的(环意义下)最小的点是 tt,这说明 i→t→nxtii\to t\to nxt_i,而由于能扩展到 ii 必然有 t→it\to i,那么 i,ti,t 在同一个 SCC 中。

可以看出这个过程跟 SCC 有很大关系,我们有了一个新的暴力:不断加入新点的同时维护 SCC,形状呈一条 SCC 链,每次判断最后一个 SCC 能不能到新点,每次合并一个后缀的 SCC,这个算法单次 O(nα)\mathcal O(n\alpha),一共是平方的。

正解

考虑如何优化这个算法,由于可达关系是闭包,考虑断环为链后,从后往前加入每个点,计算答案,在统计到每个点靠前出现的位置时我们会统计到答案。

想象一下形态,你发现每个可达关系都是一条平铺在环上的链,每次我们加了一个新点和一些新边,要尝试合并前两条链。

考虑合并前两条链的条件:前一条链的最后一个 SCC 能到后一条链的第一个点(不是第一个 SCC,因为此时只能顺次扩展)。

由于是新边造成了合并,又是最后一个 SCC 造成了合并,所以如果需要合并那么第一条链只有一个 SCC。

综上,每条链只需记录最大的起点 valcval_{c},使得该起点有一条跨 SCC 的返祖边(指向前面的边),顺便每个点维护最大的小于它的入点 prexpre_x。

每次我们先尝试合并第一条链的前两个 SCC,判断条件是第一条链的 valval 要大于该环的最后一个点,合并后记得清空第一条链的 valval。

若第一条链只剩一个 SCC,那么我们尝试合并前两条链,判断条件是 prethe first one of the next chainpre_{\text{the first one of the next chain}} 存在(只要存在就必定连到前面)。

建议参照第一篇题解的代码。

曾经的我以为这种题需要发明一个类 tarjan 算法来解决,但其实它的结构足以用 SCC 类似物描述,也就是说图论的连通性部分是有其分析算法的。

P6880 [JOI 2020 Final] オリンピックバス

给定有向图,你可以在出发前选择一条边翻转并把边权从 wiw_i 改为 rir_i,求所有情况下 11 到 nn 最小代价。

n≤200,m≤5×104n\le 200,m\le 5\times 10^4。

若你翻转的边在最短路树上,那么原先的最短路体系就不能用了,一共 nn 次,你需要重算最短路,使用平方 dijkstra\rm dijkstra 即可。

若不在最短路树上,由于你想利用这条边,用原图最短路拼一下即可。

P8456 「SWTR-8」地地铁铁

给定一张 nn 个点,mm 条边的无向连通图。每条边标有 D 或 d。

定义无序点对 (x,y)(x, y) 是「铁的」,当且仅当 x≠yx \neq y 且 x,yx, y 之间存在同时出现 D 和 d 的简单路径。

小 A 深知自由组合定律 DdTt 的重要性,所以他让你对这样的点对计数。

注意:

  • 简单路径定义为不经过重复 节点 的路径。
  • 保证图无自环,可能有重边。

对于 100%100\% 的数据:

  • 2≤n≤4×1052\leq n \leq 4\times 10 ^ 5,n−1≤m≤106n - 1\leq m\leq 10 ^ 6。
  • 1≤x,y≤n1\leq x, y\leq n。
  • c∈{D,d}c\in \{\texttt{D}, \texttt{d}\}。

这题实质上给了你三个图,D 图 d 图还有放在一起的图,需要同时想想在不同的图上我们能做什么。

首先看到图没什么头绪,想想点双还是边双还是 dfs 树。

判断点双还是边双有一个好方法:点双实质上是对边的连通性进行分类,含有点不交字样,边双对点的连通性进行分类,含有边不交字样。

这题是点不交,且边有两类,那缩个点双先。

我们猜测若点双内同时有两种边,则点双内两两合法,但这显然是错的,易得反例是 1→2→31\to 2\to 3 都是 D 边,1→31\to 3 是 d 边。

上文是自己的思考,下面来说题解:

事实上,上文的思考已经相当接近正解。

考虑上文的反例出现的原因:点双内只有两个点有混色出边,这样在 check 这个点对的时候,如果你想要切换颜色就必须走到终点,那么你就寄了。

剩下的情况会不会出现反例呢,直观感受是没有的,感性理解是你可以走到新的切换颜色点去切换。

所以这种特殊点双贡献是 (siz2)−1\binom {siz}2-1,剩的合法点双是 (siz2)\binom{siz}2。

接下来考虑跨点双的点对,每个点双可以分为纯黑纯白和混色,直观感受是只要跨过的点双存在两种颜色就可以,这个也是好证的,纯黑纯白显然成立,混色至少可以选一种颜色。

那怎么统计这些点对呢,我们建出圆方树,可以考虑 dsu on tree。

但是那属于学魔怔了,每个点到当前子树的根只有纯黑、纯白、混色三种,信息量是 O(1)\mathcal O(1) 的,所以写个类 dp\rm dp 式合并信息就可以了。

实现上有一些边界细节,不妨统计总数减不合法点对数,这样我们只需统计每个纯黑连通块和纯白连通块的 (siz2)\binom{siz}{2},以及特殊点双的个数。

P10790 [NOI2024] 树形图


图上复杂路径

经典的题目是异或,这里讨论一些模意义下的性质。

经典性质:无向图上的所有环的线性组合就是 dfs\rm dfs 上所有返祖边的线性组合。

典题:欧拉子图

给定一个图,求欧拉子图数量。

欧拉子图是若干边不交的回路(圈)。

每个连通块分开考虑,非树边随便选,奇数次树边要选偶数次不选,也就是树边可以调整自适应。

所以就算 2m−n−f2^{m-n-f},ff 是联通块数。

#508. 「LibreOJ NOI Round #1」失控的未来交通工具

一个带边权无向图,有两种操作:加边以及询问在 x,x+b,...,x+(c−1)bx,x+b,...,x+(c-1)b 这些数中,有多少数存在一条从 uu 到 vv 的路径长度与之模 mm 同余(可以不是简单路径)。

n,q≤106n,q\le 10^6。

考虑有无反复走可以消掉的性质,显然走 2m2m 次可以消掉,所以我们可以复合全图任意一个环。

注意到是无向图,所以每条边都是一个二元环,我们可以加上全图任意一条边的二倍。

所以 mm 是奇数已经解决了,22 有逆,只需关心边无需关心环,直接维护联通块的 gcd⁡\gcd 即可。

但 mm 是偶数就需要关心每个环,我们需要关心生成树上的到根的和,动态树?带权并查集!

求解答案只需跑 exgcd 实现等差数列求交即可。

注意带权并查集的权值,fa[y]=x,val[x]=vx+vy+w。

#E. 前行-这题因为断网我搬了整整四次(骂骂咧咧)& [AGC031F] Walk on Graph

有一张 nn 个点 mm 条边的无向连通图 GG,每条边有长度 LiL_i,有一个人在上面游走。

有 qq 组询问,每组询问给出 si,ti,ris_i,t_i,r_i,询问是否存在一条从 sis_i 出发到 tit_i 结束且长度为 rir_i 的路径(不要求简单路径)。其中路径长度的定义为:假设走过了的边长度为 L1,L2,⋯ ,LkL_1,L_2,\cdots, L_k,则这条路径的长度为 (∑i=1kLi×2i−1) mod MOD(\sum_{i=1}^kL_i\times 2^{i-1}) \bmod MOD。

1≤n,m,q≤50000,MOD≤1061\leq n,m,q\leq 50000,MOD\leq 10^6 且 MODMOD 为奇数。

对骆老师伟大题解的小小注脚:

时间维极其烦人,我们直接把路径倒过来,就变成每次 x←2x+wx\gets 2x+w,这样我们只关心当前权值。

奇数  mod \bmod 保证了 22 有逆元,所以我们暂且不用担心乘若干个 22 会使可能的取值变少。

最近讲图论刚讲了个类似的,那我们肯定往上面想,s→ts\to t 的简单路径拼上点什么东西。

考虑一些节外生枝的东西能不能消掉,考虑反复走 kk 次:2kx+L∑i=0k−12i2^kx+L\sum_{i=0}^{k-1} 2^i,我们主要关心 ∑2i\sum 2^i 能不能凑出 00,等比数列求和化一下是 2k−12^k-1 状物,而 2⊥ mod 2\perp \bmod,那显然 2φ(mod)−1≡02^{\varphi(\text{mod})}-1\equiv0,所以这里的结论也是一样的,我们仍然可以拼上全图中任意一个环,中间的多余路径可以通过反复走而消掉。

证明了这个性质后其实也证明了 每条路径都是可逆的,即如果我们考虑 (i,j)(i,j) 表示当前在 ii 权值是 jj 的状态,那么这其实是一个无向图。

在 (i,j)(i,j) 的意义下继续考虑连通性,你发现一条边的作用其实是做了一个 置换(没有一对多或多对一),这个置换可以用简单的 2x+w2x+w 来描述,置换的复合也可以只用 kx+bkx+b 来描述。

我们可以对原图跑生成树,每个点的值都映射回 11 号点,可以把状态精简为 mod\text{mod} 个,假设映射到 11 的函数是 aux+bua_ux+b_u,每条边 (u,v,w)(u,v,w) 的效果都是 ∀x,aux+bu↔av(2x+w)+bv\forall x,a_ux+b_u\leftrightarrow a_v(2x+w)+b_v,然后在这个图上跑并查集。

每次要在这个图上连 x→kx+bx\to kx+b,k,bk,b 都不是定值,完全无法战胜。

这个思路的问题是完全没有用到 22 的性质,或者说仅仅利用了可逆性。

尝试考虑环但你发现一个环从哪里开始都不知道,并且你也不知道从哪里开始是否等价。

不妨先考虑二元环(一条边)的简单情况。

走回去再走回来的效果是 x→4x+3wx\to 4x+3w,所以全图(上文已证,我们可以自由符合全图的每个环)如果有两条 w1,w2w_1,w_2 的边,那么 4x+3w1↔x↔4x+3w24x+3w_1\leftrightarrow x\leftrightarrow 4x+3w_2,由于 4x4x 可逆,所以 x+3w1↔x+3w2x+3w_1\leftrightarrow x+3w_2,也就是说我们可以自由把数加上 3(w1−w2)3(w_1-w_2)。

根据裴蜀定理,我们可以自由加上 3gcd⁡i=1n(wi−w1)3\gcd_{i=1}^n(w_i-w_1),以下简称为 3g3g,所有东西都可以  mod  3g\bmod \ 3g。

由于 gg 是差的 gcd⁡\gcd,所以每个 ww 都可以变成 z+kg(k≤2)z+kg(k\le2),其中 z=w1 mod gz=w_1\bmod g 。

现在再看边的影响:(u,x)→(v,2x+z+kg)(u,x)\to (v,2x+z+kg),也就是 (u,x−z)→(v,2x−z+kg)(u,x-z)\to(v,2x-z+kg),我们把值域平移 zz,即现在用 (u,x)(u,x) 表示以前的 (u,x−z)(u,x-z)(想起了刚上高一天天换元的文化课时光)。

那就是 (u,x)→(v,2x+kg)(u,x)\to (v,2x+kg),一样的套路,我们转回来:(u,x)→(u,2(2x+kg)+kg)=(u,4x)(u,x)\to(u,2(2x+kg)+kg)=(u,4x)。

(u,x)(u,x) 都与 (u,4x)(u,4x) 联通了,这个性质太强了,发现 (u,z)(u,z) 能到的状态都是 az+bgaz+bg,aa 是 22 的幂,bb 是 <3<3 的数。

由于 xx 与 4x4x 联通,将 az+bgaz+bg 不断乘上 4−14^{-1},于是我们也只需关心 a∈[1,2]a\in[1,2] 的值了,共 6n6n 个状态。

如果把 22 变成 pp,那么前文的另一个思路直接做复杂度是 n+p2n+p^2 的,直接在图上跑是 npnp 的。

一些细节:改完定义之后边的操作就是 (u,x)→(v,2x+kg)(u,x)\to (v,2x+kg) 了,也就是 (u,x)→(v,2x+w−z)(u,x)\to (v,2x+w-z),询问的值要加上 zz。

平面图

三角剖分图可以三染色判定。

#554. 「LibreOJ Round #8」MIN&MAX II

给定排列,每个点向左右第一个比它小/大的点连边,qq 次询问只保留一个区间的点和边,问染色数(至少需要几种颜色可以将点染色,每条边两边不一样)。

n,q≤3×105n,q\le 3\times 10^5。


CF1062F Upgrading Cities

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量