[BZOJ 3925][ZJOI2015]地震后的幻想乡

danihao123 posted @ 2018年2月13日 18:00 in 题解 with tags 数学分析 ZJOI bzoj 状压dp 概率与期望 连续型期望 , 182 阅读
转载请注明出处: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}
\]
里面有两大块定积分,前一块还看起来蛮好求的,但后面一块……
不就是\(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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter