[BZOJ 3925][ZJOI2015]地震后的幻想乡
赛艇，赛艇.jpg
首先这个问题的本质就是让你求一个边权在[0,1]间均匀随机分布的无向图的MST的最大边边权的期望……
有一个很经典的式子：
E=∫10p(≥x)dx
然后考虑那个p咋整。
首先对于每个包含1的点集（我们不妨假设是从点1开始扩展）S，式子可以这么写（这里不妨用T来表示两个点集间的边的数目）：
pS,x=∑1∈S0⊂S(1−x)T(S0,S−S0)(1−pS0,x)
显然答案是∫10pS,xdx，但这玩咋求……
然后我们定义一个状态d：
dS,k=∫10(1−x)kpS,xdx
把其中的p展开，整理一下，得到：
dS,k=∑1∈S0⊂S(∫10(1−x)T(S,S−S0)+kdx−∫10(1−x)T(S,S−S0)+kpS0,xdx)
里面有两大块定积分，前一块还看起来蛮好求的，但后面一块……
不就是dS0,T(S,S−S0)+k 吗？
然后这样整个d就可以搞一波状压DP了。
然后观察dS,0（这里不妨假设S为全集）：
dS,0=∫10(1−x)0pS,xdx=∫10pS,xdx
这不就是我们要的答案吗？
至于边界处理，d{1},x全部搞成0就行。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | /************************************************************** 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;} |
