LOJ2290 「THUWC 2017」随机二分图

duyi · 2021-03-01 17:32:44 · 题解

洛谷的latex有严重的问题，请务必在我的cnblogs查看本文！

链接

LOJ2290 「THUWC 2017」随机二分图

题目链接

本题题解

设完美匹配数量的期望是 E。根据期望的定义：

根据期望的线性性，可以转化为：

暴力做法，可以 \mathcal{O}(n!) 枚举一组完美匹配，计算它出现的概率。

计算一组完美匹配出现的概率，只需要考虑这组完美匹配里的边。举个例子，你要求抛 3 次硬币，前两次都是正面朝上的概率，这个概率就是 \frac{1}{2} \cdot \frac{1}{2}，而不需要考虑第三次的结果。同理，本题里，在计算时，只需要保证当前这组完美匹配里的边都在图上出现了，而其它边是否出现则不用管。

优化上述暴力。考虑使用状压 DP。当只有 t = 0 时，可以设 \mathrm{dp}_0(i, s)，其中 s 是一个二进制状态，表示考虑了左边的前 i 个点，匹配掉了右边 s 里这些点，发生的概率。转移时枚举左边第 i + 1 个点匹配了右边的哪个点，乘上概率 \frac{1}{2}，进行转移。最后 E = \mathrm{dp}_0(n, 2^n - 1)。

当有 t = 1 和 t = 2 时，要注意到：题目限制了一组里两条边在图上的出现情况，但并未直接限制它们在完美匹配里的出现情况。例如：对于 t = 1 的两条边 (a_1, b_1),(a_2, b_2)，它们在图上要么同时出现，要么同时不出现（这是题目要求的），但在完美匹配里，可能只有 (a_1, b_1)，或只有 (a_2, b_2)，或两个都有，或两个都没有（当然，根据前面的讨论，两个都没有时不用管，我们只计算出现了的边出现的概率）。也就是说，一条边出现在图里和出现在完美匹配里，是两回事，在接下来读题解时，不要把它们搞混了。

因为涉及到要同时加入两条边，我们把 DP 状态改一改。设 \mathrm{dp}_1(s_1, s_2) 表示左边 s_1 里这些点匹配了右边 s_2 里这些点（s_1, s_2 二进制下 1 的个数相同）。但是转移时遇到麻烦了。例如我要考虑，【只有 (a_1,b_1) 出现在完美匹配里】的情况，那这个状态相当于要带一个附件要求：在此后的转移里，不能单独选 (a_2, b_2)（否则就和【(a_1, b_1)，(a_2, b_2) 同时出现在完美匹配里】这种情况重复了）。但是你又不好把这个附加要求写进 DP 状态里，于是就会算进去一些不该算的东西，导致答案错误。

怎么办？本题的精髓就在这里了。将一组 t = 1 的两条边拆开！假装它们就是 t = 0 的两组边。观察此时在计算答案时，会是什么效果：

• 如果在最终的完美匹配里只出现了 (a_1, b_1)，那在我们统计时它对概率的贡献是 \frac{1}{2}。它代表的实际情况是：(a_1, b_1) 和 (a_2, b_2) 都在图里，我们知道这种情况实际出现的概率也是 \frac{1}{2}。所以算的就是对的！
• 如果在最终的完美匹配里只出现了 (a_2, b_2)，和上一种情况同理。
• 如果在最终的完美匹配里，同时出现了 (a_1, b_1) 和 (a_2, b_2)，则统计时对概率的贡献是 \frac{1}{4}。但是它代表的实际情况是 (a_1, b_1) 和 (a_2, b_2) 都在图里，我们知道这种情况出现的概率其实是 \frac{1}{2}。所以这里就少算了 \frac{1}{4}。怎么办？根据期望的线性性，我们单独把这少算的 \frac{1}{4} 加回来就行了！所以我们新建一种转移，同时取 (a_1,b_1) 和 (a_2,b_2)，且这种转移的系数是 \frac{1}{4}。
• 如果都没出现，不用管。