图论全家桶

· · 个人记录

虚树

将原树上的关键点和其LCA抽出来独立建一棵树。

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

最小割树

定义：对原图（限制只能是无向图。。）上的点新建一棵带权树，满足任选树上两个点 s,t，路径 (s,t) 中的最小边权为 s 到 t 的最小割，且切掉这条边后产生的两个连通点集就是最小割的点集。

这个东西有点难建，一般用的是其 alternative：等价流树，即忽略掉上文中 “且” 后的要求。

性质：

设 s,t 的最小割把图割成了 L,R 两部分（点和边都算在其中，割边扔掉不管），其中一侧（不妨认为是 L）的两个点 p,q 的最小割的割边集合可以完全包含在 L 之中。

somehow，通过这个和什么其它的东西就可以得到一个算法：

在当前点集内随便选两个点 p,q，在原图里跑最小割 val=Cut(p,q)，在最小割树上 Link(p,q,val)，对割出的两个点集分别递归跑这个即可。

网络流 补充

对于求 \sum f(d_i) （f(x) 为下凸函数，d_i 满足一定限制，由网络流模型保证）一类的问题，可以将每一个 d_i 向 汇点连一系列的边，第 i 条的流量为 1，代价为 f(d_i)-f(d_i-1)。

在跑上下界网络流时，设一条边的流量可以为 [a,b]，如果有流量限制的边都没有费用，可以将一条边拆成一条流量为 a，费用为 -MAX 和一条流量为 b-a，费用为 0 的边来规避掉上下界。

p.s. 如果有费用是不是将两条边的费用都加上原费用就行啊。不知道。

最小费用可行流只需要把终止条件从 T 不可达改成到 T 的距离 >0 即可。

二分图相关

Problem

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

结论：从左侧未匹配的节点出发进行dfs，从左往右走非匹配边，从右往左走匹配边。记录经过的点。则最小点覆盖集合为 左侧未经过的节点 和 右侧经过的节点 的并。其大小恰为最大匹配。

先证其大小等于最大匹配：对于一个左侧未经过的节点，一定对应一条匹配边（不然会作为起始点dfs）。对于一个右侧经过的节点，也会对应一条匹配边（否则意味着它是dfs树的叶子，到起始节点的路径是增广路，和最大匹配矛盾）。而显然这两种方式不会映射到同一条匹配边上，所以总节点数就是最大匹配。也可以说明最小性：每条匹配边都至少需要一个点来覆盖，更少一定不行。

再证其是点覆盖：只需证明不存在左侧经过但右侧未经过的边。上一段已证明匹配边都被匹配上了。对于非匹配边，如果左侧经过，dfs的时候一定会通过这条边。

最大独立集

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

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

结论：对于一个点 x 拆 x_{in}，x_{out}，对于一条 p\rightarrow q 连 p_{out},q_{in}。满足 x_in 和 x_{out} 同在最大独立集中的 \{x\} 构成最长反链。其大小=原图的最小链覆盖

这次先证其是反链：不用证，都在独立集里了，任意两点之间不会有边。

再证其最长：记匹配边数 =m，最大独立集为 I，A 为构造出的反链。首先有 |I|=2n-m。

考虑 |I|-|A| 的意义是“x_{in} 和 x_{out} 中至少一个 \in I 的 x 个数”。\leq n。 所以 |A|\geq n-m。

而 n-m 同时是原图最小链覆盖。而最长反链中不可能有两个点在一个链里，所以 |A|\leq n-m。所以 |A|=n-m，而且 A 是最长反链。

Johnson && Primal-Dual

Johnson

要复刻 Floyd 干的事情，求全源最短路，但是不想承受 n^3 的复杂度。Johnson 是一个 nm\log m 的解法。

考虑建超级源点，向所有点连边权为 0 的边，跑超级源点的单源最短路，到点 i 的距离设为 h_i。将图上的每条边的边权 w(u,v) 修改为 w(u,v)+h_u-h_v。设原图上的任意一条路径长度为 W(u,v)，则同样的路径在修改后的图上一定是 W(u,v)+h_u-h_v。而且修改后的图上边权非负，n 遍 Dijkstra 就做完了。

考虑到 h 叫“势能函数”，不管 h 长什么样子，找到的最短路是原图最短路这一事实是显然的。对于边权非负，因为 h 是跑最短路出来的，所以有 h_v\leq w(u,v)+h_u。移项可得。

Primal-Dual

其实并没有理解这个名字和线性规划的对偶问题有什么关系（

仍然，考虑使用 Dijkstra 替代费用流中的 SPFA。仍然考虑势能函数，但是因为过程中会激活/失效一些边（容量为0的），且不管边是否激活都将其边权变为正是不可能的（一旦网络非DAG便必然出负环），所以需要动态更新势能。

记当前的势能为 h_i，到源点的距离为 dis_i（算上势能差的假距离），则让下一轮的势能 h'_i\leftarrow h_i+dis_i 即可：

如果边 (i,j) 在最短路上，则 dis_i+(w(i,j)+h_i-h_j)=dis_v。其反边 (j,i) 下一轮有可能激活，此时 w(j,i)+h'_j-h'_i=-w(i,j)+(h_j+dis_j)-(h_i+dis_i)，根据上式，=0。

对于已经激活的边，有 dis_i+(w(i,j)+h_i-h_j)\geq dis_v，变形得 w(i,j)+h'_i-h'_j\geq 0。所以没问题。

初始的 h_i 直接 SPFA，如果费用流连边都是正费用当然也可以 Dijkstra。

对于这道题，一个显然的方式是拆点，对于一个点 i 拆成 in_i 和 out_i，之间连一条 (cap=1,cost=a_i)，一条 (cap=+\infty,cost=0)。然后是最大费用最大流，将所有费用取相反数。但是过不去，因为只能跑spfa，是 O(nmf) 的。即使原始对偶，也是 O(nm+mf\log m)。

非常聪明的一步：缩点，成为了一个DAG。DAG有什么性质？有拓扑序，可以变成一个单向的序列问题。具体地，考虑最小化“代价”而非最大化“得分”。如果从拓扑序为 i 的 SCC 走到拓扑序为 j 的 SCC，则 [i+1,j-1] 的SCC便走不到了，可以视这条边的代价为 \sum_{k=i+1}^{j-1}val_k。这时 in_i 向 out_i 的边为 (cap=1,cost=0)，(cap=+\infty,cost=val_i)。这样边权全正了。

耳分解

定义一个耳为一个（边数 \geq 2 的？）环或链。

如果一个图 G 是可耳分解的，则代表可以从一个环通过以下操作生成：

  1. 选取图中的两个点 x_1,x_k（可以相同）；

  2. 选取不在图中的 x_1,x_2,\cdots,x_{k-1}，使 x_0,x_1,\cdots,x_k 成为一个耳。

无向图可耳分解 \Leftrightarrow 无向图边双连通。

考虑将边双转化为耳分解，dp 可耳分解的图和其最小代价。

设 f_{S,i,j} 表示当前被添加到图中的点集为 S，未完成的一个耳的端点为 i，最后要把它接到 j 上。转移细节较多，共 O(n^32^n)。

LGV 引理

一句话就是，相交路径集合对行列式的贡献之和为 0。

设 G 为一带权 DAG，w(u,v) 为边 (u,v) 的边权。

设 \omega(P) 为路径 P 的权值（所有边权之积），即 \prod\limits_{(u,v)\in P}w(u,v)。

设 e(u,v) 为所有起点为 u，终点为 v 的路径权值和，即 \sum\limits_{P:u\rightsquigarrow v}\omega(P)。

设起点、终点集合分别为 A,B，大小均为 n。

设 \mathcal{S} 为一组不相交路径集合 \{P_i|P_i:A_i\rightsquigarrow B_{\sigma(i)}\land \forall i\neq j,P_i\cap P_j=\varnothing\}。

则 LGV 引理如下：

\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)

证明：

\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 提到了最前面。

设 \mathcal{P}=\mathcal{S}\cup\mathcal{T}，\mathcal{S} 定义如上，\mathcal{T}=\complement_\mathcal{P}\mathcal{S}，即有相交的路径集合。

我们宣称，\mathcal{T} 对上式的贡献为 0，即

\sum_{\mathcal{T}}(-1)^{\pi(\sigma(\mathcal{T}))}\prod_{i=1}^{n}\omega(\mathcal{T}_i)=0

考虑对于一个 \mathcal{T}，设其中两条相交的路径为 P_1,P_2，使得 P_1:A_1\rightsquigarrow u\rightsquigarrow B_1,P_1:A_1\rightsquigarrow u\rightsquigarrow B_2。

我们可以让 P'_1:A_1\rightsquigarrow B_2,P'_2:A_2\rightsquigarrow B_1，得到 \mathcal{T}'。因为这步操作实际上交换了 \sigma_1 和 \sigma_2，故 \mathcal{T}' 的系数和 \mathcal{T} 反号，而贡献恰好相等，故抵消。

还需证明可以构造出双射，但是这太烦了且比较容易感性接受。略过。

另外，只要 w(u,v) 在交换环里就行，不一定非得是整数。

SCC 计数

大体思路是，考虑 SCC 等价于缩点之后必为 DAG。遂容斥，进行类似 DAG 计数状物。

设 f_S 表示 S 缩点后为一个孤立点的方案数，即题目所求；E_{S,T} 表示 S\to T 的边数。

设 \lambda_{S,k} 表示使得 S 缩点后为 k 个孤立点（即由 k 个不交的 SCC 组成）的方案数，g_{S}=\sum (-1)^{k+1}\lambda_{S,k}。

则有：

f_{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}}

道理是，考虑计算不合法情况，选取一个集合 T，钦定 T 缩点后成为若干个入度为 0 的点。容斥系数 g 已经自带了。T 到 S/T 与 S/T 内部都可以随便连边。比较搞笑的是 f_S 自己也被算进去了，在式子里要去掉。

然后计算 g_S：

g_S=f_S-\kern{-23px}\sum_{\substack{T\sub S\\\operatorname{lowbit}(T)=\operatorname{lowbit}(S)}}\kern{-23px}f_{T}g_{S-T}

由于 g 的 (-1)^{k+1} 容斥系数，故添加 f_{S/T} 的新 SCC 时系数为 -1。lowbit 相等是因为各个 SCC 不区分，会被重复计算 k 次。直接规定某个 SCC 是新加的就可以了。

最后只剩 E：

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)