省选联考 2025 D2T2 题解

20_200 · 2025-03-08 12:05:38 · 题解

一年前，你首次亮相，我满怀悲痛的走出考场。

一年的岁月磨灭了那悲痛的痕迹，我时不时幻想着一年后的那天能够重塑时光。

而当这一天真的来临，你竟然再次出现，虽经历岁月侵蚀，但核心却仍然保持不变。

我却只能在无尽的代码中苦苦挣扎，面对着即便重塑时光依旧无法改变的必死结局，追忆这逝去的青春岁月。

题意

给定一个 n 个点 m 条边的带权无向图，现在每条边对应的正反向边都有 \frac{1}{2} 的概率被删除，求删边后的有向图存在最小外向生成树且其权值和等于原图最小生成树的概率。

分析

因为总方案数有限，所以直接把概率转计数，最后再除以 2^{2m}，虽然直接算概率能省去很多系数但是概率全是分数debug过于困难。

定义 A/B 表示集合 A 去掉集合 A\cap B 得到的集合。

定义一个有向图弱连通当且仅当将其所有边看作无向图后连通，有向图的 MST 为其最小外向生成树。

定义一个有向图合法当且仅当将其存在 MST，可以发现这等价于将其缩点后只有一个入度为零的强连通分量。接下来我们只讨论合法的有向图。

定义合法有向图的关键点集为可以作为MST的根的点集，显然该点集强连通。

显然删边后的有向图 MST 的权值和大于等于原图 MST，而根据 Kruskal 算法的原理，两者相等的必要条件是对任意 i\in[1,m]，加入所有边权 \le i 的边，得到的图的弱连通性与原图加入所有边权 \le i 的边后的图相同，且每个弱连通分量都合法。

我们对每个 i 的每个弱连通分量分别考虑（注意因为原图的边是给定的，所以这里的弱连通分量是固定的），我们需要选择一些该弱连通分量中边权为 i 的边，把若干个由边权 <i 的边组成的合法弱连通分量合并成一个。

对于一个边权-弱连通分量 k，设其点集为 A_k，对应的边权为 v_k，其合并集为 C_k，即 A_k=\cup_{x\in C_k}A_x 的，该连通分量中权值等于 v_k 的边集为 E_k。现在只考虑 E_k 中的边，定义两端点不在同一个 A_x，且终点为某个 A_x 的关键点的边称为关键边。

由于在任意一个 MST 中，每个 A_x 的入度不超过一，因此，最终的 MST 只可能包含关键边。那么对于上面所说的必要条件，可以发现，若只考虑关键边，则上述条件变为充要条件，因为对每个边权-弱连通分量 k，从关键点出发就可以充分利用边权 \le v_k 的所有边，而关键边都会连接到关键点，若仅靠关键边就能保持弱连通和合法性，则可以选择和原图数量相同的边权为 v_k 的边并充分利用边权小于 v_k 的边，使得 A_k 的 MST 等于原图。

而一条边是否关键只与其对应 A_x 的关键点集有。所以，对每个 k，将 x\in C_k 的每个 A_x 看作一个点，这些点和关键边组成一个有向图，则选择的关键边应使得该图合法，而 A_k 的关键点集为该图的关键点集对应的 A_x 对应的关键点集的并集。

那么现在这题的思路就很明确了，状态只需要记录关键点集，然后由于关键点集的强连通性，还需要做强连通计数。

DP

这个部分基本是和重塑时光一脉相承的东西，核心思想就是容斥入度为零的点（强联通分量）。

考虑设计 dp 状态，设 \text{dp}_{k,S} 表示选择两端点都在 A_k 中的边使得 A_k 合法且其关键点集是 S 的方案数。

下面计算某一个 k 的 dp，以下讨论的 S 为 A_k 的子集。

定义 cnt(S,T)=2^{\sum[x\in S][y\in T][(x,y)\in E_k]}。

设 u_S 表示所有 S\cap A_x\neq\varnothing 的 x 构成的集合，d_S=\cup_{x\in u_S}A_x。

设 f_S 表示对于 x\in u_S，A_x 的关键点集为 S\cap A_x，用关键边将 u_S 合并成一个强连通分量的方案数。

设 g_S=\sum_{T_1,T_2,\dots,T_x}(-1)^x\prod_{i=1}^xf_{T_i}，其中 T_1,T_2,\dots,T_x 是 S 的无序划分，且对于 i\neq j，u_{T_i}\cap u_{T_j}=\varnothing，即 S 带容斥系数的划分的 f 的贡献和。