专栏文章

图论全家桶

aabv3Rpkg
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miql94yi
此快照首次捕获于
2025/12/04 06:38
3 个月前
此快照最后确认于
2025/12/04 06:38
3 个月前
查看原文

虚树

将原树上的关键点和其LCA抽出来独立建一棵树。
先求得原树dfn序，并将所有关键点按照dfn排序。求得相邻两项的LCA。将LCA和关键点一起再次排序以后，枚举相邻两项，连 LCA⁡(pi,pi+1)→pi+1\operatorname{LCA}(p_i,p_{i+1})\rightarrow p_{i+1}。证明可以感性理解。O(nlog⁡n)O(n\log n)。

最小割树

定义：对原图（限制只能是无向图。。）上的点新建一棵带权树，满足任选树上两个点 s,ts,t，路径 (s,t)(s,t) 中的最小边权为 ss 到 tt 的最小割，且切掉这条边后产生的两个连通点集就是最小割的点集。
这个东西有点难建，一般用的是其 alternative：等价流树，即忽略掉上文中 “且” 后的要求。
性质：
设 s,ts,t 的最小割把图割成了 L,RL,R 两部分（点和边都算在其中，割边扔掉不管），其中一侧（不妨认为是 LL）的两个点 p,qp,q 的最小割的割边集合可以完全包含在 LL 之中。
somehow，通过这个和什么其它的东西就可以得到一个算法：
在当前点集内随便选两个点 p,qp,q，在原图里跑最小割 val=Cut(p,q)val=Cut(p,q)，在最小割树上 Link(p,q,val)Link(p,q,val)，对割出的两个点集分别递归跑这个即可。

网络流 补充

对于求 ∑f(di)\sum f(d_i) （f(x)f(x) 为下凸函数，did_i 满足一定限制，由网络流模型保证）一类的问题，可以将每一个 did_i 向 汇点连一系列的边，第 ii 条的流量为 11，代价为 f(di)−f(di−1)f(d_i)-f(d_i-1)。
在跑上下界网络流时，设一条边的流量可以为 [a,b][a,b]，如果有流量限制的边都没有费用，可以将一条边拆成一条流量为 aa，费用为 −MAX-MAX 和一条流量为 b−ab-a，费用为 00 的边来规避掉上下界。
p.s. 如果有费用是不是将两条边的费用都加上原费用就行啊。不知道。
最小费用可行流只需要把终止条件从 TT 不可达改成到 TT 的距离 >0>0 即可。

二分图相关

Problem

最小点覆盖（Ko¨nig\mathrm{K\ddot{o}nig}）

结论：从左侧未匹配的节点出发进行dfs，从左往右走非匹配边，从右往左走匹配边。记录经过的点。则最小点覆盖集合为 左侧未经过的节点 和 右侧经过的节点 的并。其大小恰为最大匹配。
先证其大小等于最大匹配：对于一个左侧未经过的节点，一定对应一条匹配边（不然会作为起始点dfs）。对于一个右侧经过的节点，也会对应一条匹配边（否则意味着它是dfs树的叶子，到起始节点的路径是增广路，和最大匹配矛盾）。而显然这两种方式不会映射到同一条匹配边上，所以总节点数就是最大匹配。也可以说明最小性：每条匹配边都至少需要一个点来覆盖，更少一定不行。
再证其是点覆盖：只需证明不存在左侧经过但右侧未经过的边。上一段已证明匹配边都被匹配上了。对于非匹配边，如果左侧经过，dfs的时候一定会通过这条边。

最大独立集

显然独立集的补集是点覆盖，所以最大独立集便是上述点集的补集。

偏序集最长反链（Dilworth\mathrm{Dilworth}）

结论：对于一个点 xx 拆 xinx_{in}，xoutx_{out}，对于一条 p→qp\rightarrow q 连 pout,qinp_{out},q_{in}。满足 xinx_in 和 xoutx_{out} 同在最大独立集中的 {x}\{x\} 构成最长反链。其大小=原图的最小链覆盖
这次先证其是反链：不用证，都在独立集里了，任意两点之间不会有边。
再证其最长：记匹配边数 =m=m，最大独立集为 II，AA 为构造出的反链。首先有 ∣I∣=2n−m|I|=2n-m。
考虑 ∣I∣−∣A∣|I|-|A| 的意义是“xinx_{in} 和 xoutx_{out} 中至少一个 ∈I\in I 的 xx 个数”。≤n\leq n。 所以 ∣A∣≥n−m|A|\geq n-m。
而 n−mn-m 同时是原图最小链覆盖。而最长反链中不可能有两个点在一个链里，所以 ∣A∣≤n−m|A|\leq n-m。所以 ∣A∣=n−m|A|=n-m，而且 AA 是最长反链。

Johnson && Primal-Dual

Johnson

要复刻 Floyd 干的事情，求全源最短路，但是不想承受 n3n^3 的复杂度。Johnson 是一个 nmlog⁡mnm\log m 的解法。
考虑建超级源点，向所有点连边权为 00 的边，跑超级源点的单源最短路，到点 ii 的距离设为 hih_i。将图上的每条边的边权 w(u,v)w(u,v) 修改为 w(u,v)+hu−hvw(u,v)+h_u-h_v。设原图上的任意一条路径长度为 W(u,v)W(u,v)，则同样的路径在修改后的图上一定是 W(u,v)+hu−hvW(u,v)+h_u-h_v。而且修改后的图上边权非负，nn 遍 Dijkstra 就做完了。
考虑到 hh 叫“势能函数”，不管 hh 长什么样子，找到的最短路是原图最短路这一事实是显然的。对于边权非负，因为 hh 是跑最短路出来的，所以有 hv≤w(u,v)+huh_v\leq w(u,v)+h_u。移项可得。

Primal-Dual

其实并没有理解这个名字和线性规划的对偶问题有什么关系（
仍然，考虑使用 Dijkstra 替代费用流中的 SPFA。仍然考虑势能函数，但是因为过程中会激活/失效一些边（容量为0的），且不管边是否激活都将其边权变为正是不可能的（一旦网络非DAG便必然出负环），所以需要动态更新势能。
记当前的势能为 hih_i，到源点的距离为 disidis_i（算上势能差的假距离），则让下一轮的势能 hi′←hi+disih'_i\leftarrow h_i+dis_i 即可：
如果边 (i,j)(i,j) 在最短路上，则 disi+(w(i,j)+hi−hj)=disvdis_i+(w(i,j)+h_i-h_j)=dis_v。其反边 (j,i)(j,i) 下一轮有可能激活，此时 w(j,i)+hj′−hi′=−w(i,j)+(hj+disj)−(hi+disi)w(j,i)+h'_j-h'_i=-w(i,j)+(h_j+dis_j)-(h_i+dis_i)，根据上式，=0=0。
对于已经激活的边，有 disi+(w(i,j)+hi−hj)≥disvdis_i+(w(i,j)+h_i-h_j)\geq dis_v，变形得 w(i,j)+hi′−hj′≥0w(i,j)+h'_i-h'_j\geq 0。所以没问题。
初始的 hih_i 直接 SPFA，如果费用流连边都是正费用当然也可以 Dijkstra。
对于这道题，一个显然的方式是拆点，对于一个点 ii 拆成 iniin_i 和 outiout_i，之间连一条 (cap=1,cost=ai)(cap=1,cost=a_i)，一条 (cap=+∞,cost=0)(cap=+\infty,cost=0)。然后是最大费用最大流，将所有费用取相反数。但是过不去，因为只能跑spfa，是 O(nmf)O(nmf) 的。即使原始对偶，也是 O(nm+mflog⁡m)O(nm+mf\log m)。
非常聪明的一步：缩点，成为了一个DAG。DAG有什么性质？有拓扑序，可以变成一个单向的序列问题。具体地，考虑最小化“代价”而非最大化“得分”。如果从拓扑序为 ii 的 SCC 走到拓扑序为 jj 的 SCC，则 [i+1,j−1][i+1,j-1] 的SCC便走不到了，可以视这条边的代价为 ∑k=i+1j−1valk\sum_{k=i+1}^{j-1}val_k。这时 iniin_i 向 outiout_i 的边为 (cap=1,cost=0)(cap=1,cost=0)，(cap=+∞,cost=vali)(cap=+\infty,cost=val_i)。这样边权全正了。

耳分解

定义一个耳为一个（边数 ≥2\geq 2 的？）环或链。
如果一个图 GG 是可耳分解的，则代表可以从一个环通过以下操作生成：
  1. 选取图中的两个点 x1,xkx_1,x_k（可以相同）；
  2. 选取不在图中的 x1,x2,⋯ ,xk−1x_1,x_2,\cdots,x_{k-1}，使 x0,x1,⋯ ,xkx_0,x_1,\cdots,x_k 成为一个耳。
无向图可耳分解 ⇔\Leftrightarrow 无向图边双连通。
考虑将边双转化为耳分解，dp 可耳分解的图和其最小代价。
设 fS,i,jf_{S,i,j} 表示当前被添加到图中的点集为 SS，未完成的一个耳的端点为 ii，最后要把它接到 jj 上。转移细节较多，共 O(n32n)O(n^32^n)。

LGV 引理

一句话就是，相交路径集合对行列式的贡献之和为 00。
设 GG 为一带权 DAG，w(u,v)w(u,v) 为边 (u,v)(u,v) 的边权。
设 ω(P)\omega(P) 为路径 PP 的权值（所有边权之积），即 ∏(u,v)∈Pw(u,v)\prod\limits_{(u,v)\in P}w(u,v)。
设 e(u,v)e(u,v) 为所有起点为 uu，终点为 vv 的路径权值和，即 ∑P:u⇝vω(P)\sum\limits_{P:u\rightsquigarrow v}\omega(P)。
设起点、终点集合分别为 A,BA,B，大小均为 nn。
设 S\mathcal{S} 为一组不相交路径集合 {Pi∣Pi:Ai⇝Bσ(i)∧∀i≠j,Pi∩Pj=∅}\{P_i|P_i:A_i\rightsquigarrow B_{\sigma(i)}\land \forall i\neq j,P_i\cap P_j=\varnothing\}。
则 LGV 引理如下：
∣e(A1,B1)e(A1,B2)⋯e(A1,Bn)e(A2,B1)e(A2,B2)⋯e(A2,Bn)⋮⋮⋱⋮e(An,B1)e(An,B2)⋯e(An,Bn)∣=∑S(−1)π(σ(S))∏i=1nω(Si)\begin{vmatrix} e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n) \\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n) \\ \vdots&\vdots&\ddots&\vdots \\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n) \end{vmatrix}=\sum_{\mathcal{S}}(-1)^{\pi(\sigma(\mathcal{S}))}\prod_{i=1}^{n}\omega(\mathcal{S}_i)
证明：
LHS=∑σ(−1)π(σ)∏i=1ne(Ai,Bσi)=∑σ(−1)π(σ)∏i=1n∑P:Ai⇝Bσiω(P)=∑P(−1)π(σ(P))∏i=1nω(Pi)\begin{aligned} \text{LHS}&=\sum_{\sigma}(-1)^{\pi(\sigma)}\prod_{i=1}^{n}e(A_i,B_{\sigma_i}) \\ &=\sum_{\sigma}(-1)^{\pi(\sigma)}\prod_{i=1}^{n}\sum_{P:A_i\rightsquigarrow B_{\sigma_i}}\omega(P) \\ &=\sum_{\mathcal{P}}(-1)^{\pi(\sigma(\mathcal{P}))}\prod_{i=1}^{n}\omega(\mathcal{P}_i) \end{aligned}
最后一行将上一行的最后一个 ∑\sum 提到了最前面。
设 P=S∪T\mathcal{P}=\mathcal{S}\cup\mathcal{T}，S\mathcal{S} 定义如上，T=∁PS\mathcal{T}=\complement_\mathcal{P}\mathcal{S}，即有相交的路径集合。
我们宣称，T\mathcal{T} 对上式的贡献为 00，即
∑T(−1)π(σ(T))∏i=1nω(Ti)=0\sum_{\mathcal{T}}(-1)^{\pi(\sigma(\mathcal{T}))}\prod_{i=1}^{n}\omega(\mathcal{T}_i)=0
考虑对于一个 T\mathcal{T}，设其中两条相交的路径为 P1,P2P_1,P_2，使得 P1:A1⇝u⇝B1,P1:A1⇝u⇝B2P_1:A_1\rightsquigarrow u\rightsquigarrow B_1,P_1:A_1\rightsquigarrow u\rightsquigarrow B_2。
我们可以让 P1′:A1⇝B2,P2′:A2⇝B1P'_1:A_1\rightsquigarrow B_2,P'_2:A_2\rightsquigarrow B_1，得到 T′\mathcal{T}'。因为这步操作实际上交换了 σ1\sigma_1 和 σ2\sigma_2，故 T′\mathcal{T}' 的系数和 T\mathcal{T} 反号，而贡献恰好相等，故抵消。
还需证明可以构造出双射，但是这太烦了且比较容易感性接受。略过。
另外，只要 w(u,v)w(u,v) 在交换环里就行，不一定非得是整数。

SCC 计数

大体思路是，考虑 SCC 等价于缩点之后必为 DAG。遂容斥，进行类似 DAG 计数状物。
设 fSf_S 表示 SS 缩点后为一个孤立点的方案数，即题目所求；ES,TE_{S,T} 表示 S→TS\to T 的边数。
设 λS,k\lambda_{S,k} 表示使得 SS 缩点后为 kk 个孤立点（即由 kk 个不交的 SCC 组成）的方案数，gS=∑(−1)k+1λS,kg_{S}=\sum (-1)^{k+1}\lambda_{S,k}。
则有：
fS=2ES,S−∑T⊆S(gT−[T=S]fS)⋅2ET,S−T+ES−T,S−Tf_{S}=2^{E_{S,S}}-\sum_{T\sube S} (g_{T}-[T=S]f_S)\cdot 2^{E_{T,S-T}+E_{S-T,S-T}}
道理是，考虑计算不合法情况，选取一个集合 TT，钦定 TT 缩点后成为若干个入度为 00 的点。容斥系数 gg 已经自带了。TT 到 S/TS/T 与 S/TS/T 内部都可以随便连边。比较搞笑的是 fSf_S 自己也被算进去了，在式子里要去掉。
然后计算 gSg_S：
gS=fS−∑T⊂Slowbit⁡(T)=lowbit⁡(S)fTgS−Tg_S=f_S-\kern{-23px}\sum_{\substack{T\sub S\\\operatorname{lowbit}(T)=\operatorname{lowbit}(S)}}\kern{-23px}f_{T}g_{S-T}
由于 gg 的 (−1)k+1(-1)^{k+1} 容斥系数，故添加 fS/Tf_{S/T} 的新 SCC 时系数为 -1。lowbit 相等是因为各个 SCC 不区分，会被重复计算 kk 次。直接规定某个 SCC 是新加的就可以了。
最后只剩 EE：
ET,S−T=ET+x,S−T−x−popcnt⁡(outx&(S−T))+popcnt⁡(inx&T)ES,S=ES−x,S−x+popcnt⁡(inx&S)+popcnt⁡(outx&S)E_{T,S-T}=E_{T+x,S-T-x}-\operatorname{popcnt}(out_x\&(S-T))+\operatorname{popcnt}(in_x\&T)\\ E_{S,S}=E_{S-x,S-x}+\operatorname{popcnt}(in_x\&S)+\operatorname{popcnt}(out_x\&S)

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...