洛谷P3343 地震后的幻想乡

传送门

题目描述

傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。

这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有 nn 个地方，那么最快的方法当然是修复 n-1n−1 条道路将这 nn 个地方都连接起来。 幻想乡这 nn 个地方本来是连通的，一共有 mm 条边。现在这 mm 条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第 ii 条边所需要的时间为 e_ie
i
​
。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个 e_ie
i
​
会是一个 00 到 11 之间均匀分布的随机实数。并且所有 e_ie
i
​
都是完全独立的。

现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那 n-1n−1 条边，同时开始修复，那么修复完成的时间就是这 n-1n−1 条边的 e_ie
i
​
的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边 e_ie
i
​
的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？

输入格式

第一行两个数 n,mn,m，表示地方的数量和边的数量。其中点从 11 到 nn 标号。

接下来 mm 行，每行两个数 a,ba,b，表示点 aa 和点 bb 之间原来有一条边。这个图不会有重边和自环。

输出格式

一行输出答案，四舍五入保留 66 位小数。

输入输出样例

输入 #1复制
5 4
1 2
1 5
4 3
5 3
输出 #1复制
0.800000

说明/提示

样例解释

对于第一个样例，由于只有四条边，幽香显然只能选择这四条，那么答案就是四条边的 e_ie
i
​
中最大的数的期望，由提示中的内容，可知答案为 0.80.8。

提示
（以下内容与题意无关，对于解题也不是必要的。）

对于 nn 个 [0,1][0,1] 之间的随机变量 x_1,x_2,…,x_nx
1
​
,x
2
​
,…,x
n
​
，第 kk 小的那个的期望值是 k/(n+1)k/(n+1)。

数据范围：

对于所有数据：n \leq 10, \ m \leq n(n-1)/2, \ n,m \geq 1n≤10, m≤n(n−1)/2, n,m≥1。

对于 15 %15% 的数据：n \leq 3n≤3。

另有 15 %15% 的数据：n \leq 10, m=nn≤10,m=n。

另有 10 %10% 的数据：n \leq 10, m=n(n-1)/2n≤10,m=n(n−1)/2。

另有 20 %20% 的数据：n \leq 5n≤5。

另有 20 %20% 的数据：n \leq 8n≤8。

上代码：

#include 
#include 
#include 
const int N = 10;
const int M = 45 + 1;
bool vis[1 << N][M];
int siz[1 << N], link[N];
double f[1 << N][M];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int lim = 1 << n;
  for (int i = 0, x, y; i < m; ++i) {
    scanf("%d%d", &x, &y);
    --x; --y;
    link[x] |= (1 << y);
    link[y] |= (1 << x);
  }
  for (int S = 1; S < lim; ++S) siz[S] = siz[S & (S - 1)] + 1;
  for (int S1 = 3; S1 < lim; ++S1) if (S1 & 1) {
    for (int S2 = (S1 - 1) & S1; S2 != 0; S2 = (S2 - 1) & S1) if (S2 & 1) {
      int T = 0;
      for (int i = 0; i < n; ++i) if ((S1 >> i) & (~S2 >> i) & 1)
        T += siz[link[i] & S2];
      for (int i = 0; i + T <= m; ++i)
        f[S1][i] += 1.0 / (i + T + 1) - f[S2][i + T];
    }
  }
  printf("%.6lf\n", f[lim - 1][0]);
  return 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