[BZOJ 3925][ZJOI2015]地震后的幻想乡
转载请注明出处：http://danihao123.is-programmer.com/
赛艇，赛艇.jpg
首先这个问题的本质就是让你求一个边权在\([0, 1]\)间均匀随机分布的无向图的MST的最大边边权的期望……
有一个很经典的式子：
\[E = \int_0^1 p(\geq x)\,\mathrm{d}x\]
然后考虑那个\(p\)咋整。
首先对于每个包含1的点集（我们不妨假设是从点1开始扩展）\(S\)，式子可以这么写（这里不妨用\(T\)来表示两个点集间的边的数目）：
\[p_{S, x} = \sum_{1\in S_0 \subset S} (1 - x)^{T(S_0, S - S_0)}(1 - p_{S_0, x})\]
显然答案是\(\int_0^1 p_{S, x}\,\mathrm{d}x\)，但这玩咋求……
然后我们定义一个状态\(d\)：
\[d_{S, k} = \int_0^1 (1 - x)^k p_{S, x}\,\mathrm{d}x\]
把其中的\(p\)展开，整理一下，得到：
\[
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
里面有两大块定积分，前一块还看起来蛮好求的，但后面一块……
不就是\(d_{S_0, T(S, S - S_0) + k}\) 吗？
然后这样整个$d$就可以搞一波状压DP了。
然后观察\(d_{S, 0}\)（这里不妨假设S为全集）：
\[d_{S, 0}=\int_0^1(1 - x)^0 p_{S, x}\,\mathrm{d}x = \int_0^1 p_{S, x}\,\mathrm{d}x\]
这不就是我们要的答案吗？
至于边界处理，\(d_{\{1\}, x}\)全部搞成0就行。
代码：
/**************************************************************
Problem: 3925
User: danihao123
Language: C++
Result: Accepted
Time:100 ms
Memory:1272 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <bitset>
typedef double R;
const int maxn = 11;
const int maxm = 50;
int edge[maxm][2];
int n, m;
R d[1 << 10][maxm];
bool vis[1 << 10][maxm];
R f(int s, int k) {
if(s == 1) return 0;
if(vis[s][k]) return d[s][k];
d[s][k] = 0;
int lit_s = s >> 1;
for(int lit_s0 = (lit_s - 1) & lit_s; ; lit_s0 = (lit_s0 - 1) & lit_s) {
int s0 = lit_s0 * 2 + 1;
int t = 0;
for(int i = 1; i <= m; i ++) {
int u = edge[i][0], v = edge[i][1];
if(((1 << u) & s) == 0 || ((1 << v) & s) == 0) continue;
if((((1 << u) & s0) == 0) ^ (((1 << v) & s0) == 0)) {
t ++;
}
}
int z = k + t;
d[s][k] += 1.00 / ((double(z)) + 1.00) - f(s0, z);
if(s0 == 1) break;
}
vis[s][k] = true;
return d[s][k];
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v); u --, v --;
edge[i][0] = u, edge[i][1] = v;
}
printf("%.6lf\n", f((1 << n) - 1, 0));
return 0;
}
Jul 16, 2023 12:44:31 AM
Rajasthan High School Every Year Academic Year Close in Month of April, Haryana , Rajasthan High School Academic Year Start in Month of Jun, So Rajasthan Board 8th Class new Students Can Download English, Hindi, Medium Subject Books Chapter wise and Full Textbooks Pdf is Available in Online Mode,Rajasthan 8th Textbook 2024 Should be Followed as the Prime Resource Throughout the year to Clear RBSE 8th Class Textbook 2024 All Doubts and Strengthen your knowledge. RBSE 8th Textbook 2024 Provides an easy Explanation for Various Concepts in the Curriculum. Our Portal are Providing the Latest Verition of Rajasthan VIII Book 2024 which is Published by the Rajasthan State Textbook Board. All the Chapters can be Downloaded in the form of PDFs.