「密集图概率」题解

问题分析

我们有一个 $n$ 个节点的有向完全图（$n \leq 12$）。每条有向边 $(x,y)$（$x \neq y$）以概率 $p_{xy}/q_{xy}$ 变为黑色，否则保持白色。我们需要计算在所有边随机变色后，满足以下条件的概率：

条件：在只考虑黑色边的子图中，从节点1到所有其他节点的最短路径长度 $\leq k$（如果不连通，则距离视为无穷大）。

问题重述

设 $G$ 是随机生成的有向图（黑色边的集合随机）。$G$ 是"密集的"当且仅当对于所有节点 $v \in \{2,\dots,n\}$，$dist_G(1,v) \leq k$，其中 $dist_G(1,v)$ 是在 $G$ 中从1到v的最短路径长度（只走黑色边），如果不连通则为无穷大。

关键观察

1. $n$ 的范围很小

$n \leq 12$ 暗示可以使用状态压缩动态规划（状压DP）。

2. 路径长度限制

从节点1出发的最短路径长度不超过 $k$。这意味着：

• 所有可达点必须在 $k$ 步内到达
• 不可达的点（距离无穷大）不满足条件

3. 有向图的最短路径

由于边权都是1，最短路径长度就是BFS的层数（跳数）。

算法框架

状态定义

我们需要考虑从节点1出发能到达哪些节点，以及它们的距离。

定义状态：$(S, d)$ 表示一个集合 $S$ 和距离 $d$，满足：

• 从节点1出发，在 $d$ 步内可以到达 $S$ 中的所有节点
• 对于 $S$ 外的节点，要么不可达，要么距离 $> d$

但更实用的方法是按BFS层次划分：

设 $L_0, L_1, \dots, L_k$ 是节点集合的一个划分：

• $L_0 = \{1\}$（起点）
• $L_i$（$1 \leq i \leq k$）：在BFS中距离为 $i$ 的节点
• $U$：距离 $> k$ 或不可达的节点

那么条件等价于：所有节点都在 $L_1 \cup L_2 \cup \dots \cup L_k$ 中（即 $U = \emptyset$）。

4. 状压DP设计

由于 $n \leq 12$，我们可以用一个 $n$ 位二进制数表示节点集合。

状态设计：设 $dp[mask]$ 表示当前已经确定距离 $\leq d$ 的节点集合为 $mask$ 的概率，其中节点1始终在 $mask$ 中。

更精细地，我们需要知道每个节点的确切距离（或至少知道它们的BFS层次）。但我们可以按层次增量构建。

更好的状态：$f[d][S]$ 表示从节点1出发，距离恰好为 $d$ 的节点集合为 $S$ 的概率，且所有距离 $\leq d$ 的节点集合已知。

但这样需要记录所有距离信息，状态数会爆炸。

5. 容斥原理方法

由于 $n$ 很小，我们可以考虑枚举所有可能的距离标签，然后计算满足该标签分配的概率。

具体来说：

• 给每个节点 $v$ 分配一个标签 $l(v) \in \{0,1,\dots,k,\infty\}$，表示从1到v的最短距离
• 要求 $l(1)=0$
• 对于黑色边 $(u,v)$，如果有 $l(u) < k$，则必须满足 $l(v) \leq l(u)+1$（因为如果有黑色边 $u→v$，那么 $dist(v) \leq dist(u)+1$）
• 对于没有黑色边的情况，没有约束

但问题是边是否黑色是随机的，我们需要计算满足这些约束的概率。

6. 转化为约束满足问题

对于固定的距离标签分配 $L: V \to \{0,1,\dots,k,\infty\}$，考虑哪些边必须是黑色/白色：

规则：

1. 如果 $l(u) < k$ 且 $l(v) > l(u)+1$，那么边 $(u,v)$ 必须是白色（否则会缩短 $v$ 的距离）
2. 如果 $l(u) < k$ 且 $l(v) = l(u)+1$，边 $(u,v)$ 可以是任意颜色
3. 如果 $l(u) = \infty$ 或 $l(v) = \infty$，边 $(u,v)$ 可以是任意颜色（因为无穷远点不影响距离）
4. 如果 $l(u) < k$ 且 $l(v) \leq l(u)$，边 $(u,v)$ 可以是任意颜色

但还有可达性要求：如果 $l(v) = d < \infty$，那么必须存在一条从1到v的黑色路径，沿着这条路径标签递增（每次+1）。这意味着对于每个距离为 $d$ 的节点 $v$，必须至少有一个前驱 $u$ 满足 $l(u)=d-1$ 且边 $(u,v)$ 是黑色。

这是关键：标签分配必须对应一个实际的BFS树（或至少一条路径）。

7. 动态规划：按距离分层

我们可以按距离从小到大处理节点：

设 $dp[S]$ 表示当前已经确定了距离 $\leq d$ 的节点集合 $S$ 的概率，且满足：

• 对于 $S$ 中的每个节点 $v \neq 1$，存在一条从1到v的黑色路径，路径上节点距离严格递增
• $S$ 中所有节点的距离 $\leq d$

转移：从 $dp[S]$ 转移到 $dp[S \cup T]$，其中 $T$ 是距离为 $d+1$ 的新节点集合。

约束：

1. 对于每个 $v \in T$，必须至少有一个 $u \in S$ 使得边 $(u,v)$ 是黑色
2. 对于 $v \in T$ 和 $w \notin S \cup T$（距离 $> d+1$），边 $(v,w)$ 可以是任意颜色，但边 $(w,v)$ 必须是白色？不一定，如果 $w$ 距离更大，$(v,w)$ 黑色可能缩短 $w$ 的距离

实际上更复杂：当我们添加 $T$ 作为距离 $d+1$ 的节点时，我们需要确保：

• 对于 $v \in T$ 和 $u \in S$：如果 $l(u)=d$，那么边 $(u,v)$ 至少有一条是黑色（为了可达性）
• 对于 $v \in T$ 和 $w \notin S \cup T$：边 $(v,w)$ 可以是任意颜色，但边 $(w,v)$ 必须是白色（否则 $v$ 的距离可能更小）

不对，如果 $w$ 的距离是 $d+2$，那么边 $(v,w)$ 黑色是可以的，但边 $(w,v)$ 黑色会使 $v$ 的距离可能变为 $d+2$？不会，因为从1到w距离 $d+2$，再到v距离 $d+3$，不影响v的距离。

关键约束是：已经确定距离的节点不能通过新发现的黑色边缩短距离。

更清晰的算法：枚举BFS树

由于 $n \leq 12$，我们可以枚举所有可能的BFS树（或更一般地，距离标签分配），然后计算该分配实现的概率。

定义：一个合法的距离分配 $(l_1,\dots,l_n)$ 满足：

1. $l_1 = 0$
2. 对于所有 $v$，$l_v \in \{0,1,\dots,k,\infty\}$
3. 如果 $l_v = d < \infty$，则存在 $u$ 使得 $l_u = d-1$ 且边 $(u,v)$ 是黑色
4. 如果 $l_v = \infty$，则对于所有 $u$ 使得 $l_u < \infty$，边 $(u,v)$ 是白色（否则 $v$ 可通过黑色边到达）

计算概率：对于固定的距离分配 $L$，计算所有边满足约束的概率乘积。

边约束总结

对于每条有向边 $(u,v)$：

• 情况1：$l_u = \infty$ 或 $l_v = \infty$
  • 如果 $l_u = \infty$ 且 $l_v < \infty$：$(u,v)$ 必须是白色（否则 $v$ 可通过 $u$ 到达，但 $u$ 不可达，矛盾）
  • 如果 $l_u < \infty$ 且 $l_v = \infty$：$(u,v)$ 必须是白色（否则 $v$ 可达）
  • 如果 $l_u = \infty$ 且 $l_v = \infty$：$(u,v)$ 可以是任意颜色
• 情况2：$l_u, l_v < \infty$
  • 如果 $l_v = l_u + 1$：$(u,v)$ 可以是任意颜色
  • 如果 $l_v \leq l_u$：$(u,v)$ 可以是任意颜色（不会缩短距离）
  • 如果 $l_v > l_u + 1$：$(u,v)$ 必须是白色（否则会缩短 $v$ 的距离）

此外，还需要可达性约束：对于每个 $v$ 满足 $l_v = d < \infty$，必须存在至少一个 $u$ 满足 $l_u = d-1$ 且边 $(u,v)$ 是黑色。

概率计算

对于固定的距离分配 $L$，设：

• $E_{\text{must\_black}}$：必须为黑色的边集合
• $E_{\text{must\_white}}$：必须为白色的边集合
• $E_{\text{free}}$：可以任意颜色的边集合

如果存在冲突（同一条边既必须黑又必须白），则该分配概率为0。

否则，概率为：

$$\prod_{(u,v) \in E_{\text{must\_black}}} P_{uv} \times \prod_{(u,v) \in E_{\text{must\_white}}} (1-P_{uv}) $$

但还要考虑可达性约束：对于每个 $v$ 满足 $0 < l_v < \infty$，至少有一个入边来自距离 $l_v-1$ 的节点且为黑色。

因此，对于每个这样的 $v$，设 $A_v = \{u: l_u = l_v-1\}$，那么需要 $A_v$ 中至少有一条边是黑色。

所以 $E_{\text{must\_black}}$ 不是独立的边集合，而是一组"至少一条"的约束。

转化为容斥

我们可以先固定哪些边是黑色（满足必须黑色的条件），然后考虑"至少一条"的约束。

具体地，对于每个 $v$ 满足 $0 < l_v < \infty$，设 $B_v \subseteq A_v$ 是实际为黑色的边集合，要求 $B_v \neq \emptyset$。

概率计算：

1. 对于必须为白色的边：一定是白色
2. 对于可以任意的边：可以是任意颜色
3. 对于 $A_v$ 中的边：至少一条黑色

设 $F$ 是自由边集合（可以任意颜色），$W$ 是必须白色边集合。

则总概率为：

$$\left(\prod_{e \in W} (1-P_e)\right) \times \sum_{\substack{B_v \subseteq A_v \\ B_v \neq \emptyset \ \forall v}} \left(\prod_{e \in \bigcup B_v} P_e \prod_{e \in A_v \setminus B_v} (1-P_e)\right) \times \left(\prod_{e \in F} 1\right) $$

最后一项 $\prod_{e \in F} 1$ 是因为自由边可以任意颜色，总贡献为1（概率和=黑+白=1）。

因此，对于每个距离分配 $L$，我们需要计算：

$$P(L) = \prod_{e \in W} (1-P_e) \times \prod_{v: 0<l_v<\infty} \left(1 - \prod_{u \in A_v} (1-P_{uv})\right) $$

其中 $\prod_{u \in A_v} (1-P_{uv})$ 是 $A_v$ 中所有边都为白色的概率，$1 - \prod_{u \in A_v} (1-P_{uv})$ 是至少一条为黑色的概率。

验证

对于样例 $n=3, k=1$：

• 合法分配：$l_1=0, l_2=1, l_3=1$
• $A_2 = \{1\}$，$A_3 = \{1\}$
• 必须白色的边：$W = \{(2,1), (3,1), (2,3), (3,2)\}$（因为 $l_2=1, l_3=1$，到距离 $\leq 1$ 的点的边必须白？检查：$(2,1)$：$l_2=1, l_1=0$，$l_1 \leq l_2$，可以任意？不对，规则：如果 $l_v \leq l_u$，边 $(u,v)$ 可以是任意颜色。所以 $(2,1)$ 可以任意。等等，我们需要重新检查）

按照规则：

• $(1,2)$：$l_1=0, l_2=1$，$l_2 = l_1+1$，可以任意（但需要至少一条黑色以满足 $l_2=1$）
• $(1,3)$：类似
• $(2,1)$：$l_2=1, l_1=0$，$l_1 \leq l_2$，可以任意
• $(3,1)$：类似
• $(2,3)$：$l_2=1, l_3=1$，$l_3 \leq l_2$，可以任意
• $(3,2)$：类似

必须白色的边：没有边必须白。 $A_2 = \{1\}$，$A_3 = \{1\}$ $P(L) = (1 - (1-P_{12})) \times (1 - (1-P_{13})) = P_{12} \times P_{13} = 1/2 \times 1/3 = 1/6$，正确。

算法实现

步骤1：枚举所有距离分配

由于 $n \leq 12$，每个节点有 $k+2$ 种可能（$0,1,\dots,k,\infty$），总状态数 $(k+2)^{n-1}$（节点1固定为0）。 对于 $n=12, k=11$，$(13)^{11} \approx 1.8\times 10^{12}$，太大。

需要优化：实际上，$\infty$ 表示不可达，而我们需要所有节点距离 $\leq k$（即没有 $\infty$），所以只需考虑 $l_v \in \{0,1,\dots,k\}$。

那么状态数为 $(k+1)^{n-1} \leq 12^{11} \approx 7.4\times 10^{11}$，仍然太大。

步骤2：优化枚举

我们可以按BFS层次枚举：

• $L_0 = \{1\}$
• 对于 $d=1$ 到 $k$，选择 $L_d \subseteq V \setminus (L_0 \cup \dots \cup L_{d-1})$
• 剩余节点 $U = V \setminus (L_0 \cup \dots \cup L_k)$ 如果非空，则分配失败（因为我们需要所有节点距离 $\leq k$）

状态数：相当于将 $n-1$ 个节点分配到 $k$ 个盒子中（每个盒子可以为空），但盒子有序（距离1,2,...,k）。 总分配数：$k^{n-1} \leq 11^{11} \approx 2.8\times 10^{11}$，仍然大。

但 $n \leq 12$，我们可以用状压DP枚举子集。

设 $f[mask]$ 表示已经处理了集合 $mask$ 中的节点（包括节点1）。用DP枚举所有可能的层次划分。

状态：$dp[d][mask]$ 表示已经确定了距离 $\leq d$ 的节点集合为 $mask$，且节点1在 $mask$ 中。 转移：$dp[d][mask] \to dp[d+1][mask \cup T]$，其中 $T \subseteq V \setminus mask$。

这样状态数是 $O(k \cdot 2^n) = O(11 \cdot 2^{12}) = O(11 \cdot 4096) \approx 45056$，可接受。

步骤3：计算概率

对于转移 $mask \to mask \cup T$（$T$ 作为距离 $d+1$ 的节点）： 需要计算概率贡献，满足：

1. 对于每个 $v \in T$，至少有一个 $u \in mask$（距离 $\leq d$）使得边 $(u,v)$ 黑色
2. 对于 $u \in mask$ 和 $v \notin mask \cup T$，边 $(u,v)$ 必须是白色（否则 $v$ 的距离可能 $\leq d+1$）
3. 其他边可以任意

但条件2太强：如果 $u$ 距离 $< d$，那么到 $v$ 的边黑色不会使 $v$ 距离 $\leq d+1$？可能会，如果 $dist(u)=t \leq d$，那么 $dist(v) \leq t+1 \leq d+1$，所以 $v$ 应该在 $mask \cup T$ 中，矛盾。因此确实必须白色。

类似地，对于 $u \in T$ 和 $v \notin mask \cup T$，边 $(u,v)$ 可以是任意颜色？如果黑色，那么 $dist(v) \leq d+2$，可能 $> d+1$，所以允许。

概率计算： 设 $S = mask$，$T$ 为新节点，$R = V \setminus (S \cup T)$。

贡献概率 $P(S,T,d)$ 包含：

1. 对于每个 $v \in T$：$p_v = 1 - \prod_{u \in S} (1-P_{uv})$（至少一个 $u\in S$ 到 $v$ 的边为黑）
2. 对于每对 $(u,v)$ 满足 $u \in S, v \in R$：边 $(u,v)$ 必须白，贡献 $(1-P_{uv})$
3. 其他边无约束（贡献1）

因此：

$$P(S,T,d) = \left(\prod_{v \in T} \left(1 - \prod_{u \in S} (1-P_{uv})\right)\right) \times \left(\prod_{u \in S} \prod_{v \in R} (1-P_{uv})\right) $$

步骤4：动态规划

初始化：$dp[0][\{1\}] = 1$（只有节点1，距离0）

对于 $d = 0$ 到 $k-1$： 对于每个状态 $dp[d][S]$，枚举 $T \subseteq V \setminus S$，$T \neq \emptyset$：

• 计算 $P(S,T,d)$
• 更新：$dp[d+1][S \cup T] += dp[d][S] \times P(S,T,d)$

最终答案：$\sum_{d=1}^k dp[d][V]$（所有节点都在距离 $\leq d$ 的集合中，且 $d \leq k$）

但注意：我们可能提前在 $d < k$ 时就包含了所有节点，这时剩余的 $d$ 到 $k-1$ 步不需要添加新节点。所以最终答案是 $dp[k][V]$。

步骤5：处理 $d$ 的维度

实际上，$d$ 的维度可以压缩，因为转移只依赖当前集合 $S$，不依赖具体的 $d$ 值。但概率计算中 $P(S,T,d)$ 依赖于 $d$ 吗？检查公式：

• $p_v = 1 - \prod_{u \in S} (1-P_{uv})$：只依赖 $S$，不依赖 $d$
• $\prod_{u \in S} \prod_{v \in R} (1-P_{uv})$：依赖 $S$ 和 $R = V \setminus (S \cup T)$，不依赖 $d$

所以 $P(S,T,d)$ 实际上与 $d$ 无关，记作 $P(S,T)$。

因此我们可以简化DP：

设 $dp[S]$ 表示已经确定了集合 $S$（节点1在 $S$ 中）的概率。 初始化：$dp[\{1\}] = 1$

转移：对于每个 $S$，枚举 $T \subseteq V \setminus S$，$T \neq \emptyset$：

$$dp[S \cup T] += dp[S] \times P(S,T)$$

其中：

$$P(S,T) = \left(\prod_{v \in T} \left(1 - \prod_{u \in S} (1-P_{uv})\right)\right) \times \left(\prod_{u \in S} \prod_{v \in V \setminus (S \cup T)} (1-P_{uv})\right) $$

最终答案：$dp[V]$（所有节点都在集合中）

但这样没有考虑距离 $\leq k$ 的限制！我们需要确保从1到任何节点的距离不超过 $k$。在DP中，每次转移添加一层节点（距离+1），所以我们最多进行 $k$ 次转移。

因此，我们需要记录层数或距离。

步骤6：恢复距离限制

设 $dp[d][S]$ 表示经过 $d$ 次转移（即距离 $\leq d$）后，集合为 $S$ 的概率。 初始化：$dp[0][\{1\}] = 1$

转移：对于 $d = 0$ 到 $k-1$，对于每个状态 $dp[d][S]$，枚举 $T \subseteq V \setminus S$：

$$dp[d+1][S \cup T] += dp[d][S] \times P(S,T)$$

最终答案：$\sum_{d=1}^k dp[d][V]$

由于我们可以在 $d < k$ 时就包含所有节点，之后不再添加节点，所以最终答案是 $dp[k][V]$。

复杂度分析

• 状态数：$O(k \cdot 2^n) = O(11 \cdot 4096) \approx 45000$
• 转移：对于每个状态 $(d,S)$，枚举 $T \subseteq V \setminus S$，有 $2^{n-|S|}$ 种选择
• 总转移数：$\sum_{S} 2^{n-|S|} = 3^n$（每个元素三种选择：在S中、在T中、不在S∪T中）
• 对于 $n=12$，$3^{12} = 531441$，可接受
• 概率计算 $P(S,T)$ 需要 $O(n^2)$ 时间预处理优化

可以通过预处理来加速概率计算。

总结

核心算法：

1. 状压DP，状态为 $(d, S)$ 表示距离 $\leq d$ 的节点集合
2. 转移时枚举新的一层节点 $T$
3. 计算转移概率 $P(S,T)$，考虑可达性约束和距离约束
4. 最终答案为 $dp[k][\text{全集}]$