[ZJOI2015]地震后的幻想乡
题目看完之后就知道不会做。
然后题目的提示十分重要：对于 n 个 [0,1] 之间的随机变量 x1,x2,...,xn，第k小的那个的期望值是 k/(n+1)。
假设我们知道 \(m\) 条边的权值，我们做一遍克鲁斯卡尔最小生成树。答案就是最小生成树中的边权最大值。也就是加入后恰好使图联通的边权。
根据题目的提示：本题的答案就是最小生成树的最大边权在 \(m\) 条边中的期望排名\(/ (m+1)\)。
所以现在就是要求最小生成树的最大边权在 m 条边中的期望排名。
然后因为期望的线性性，我们可以枚举生成树中最大边在 \(m\) 条边中的排名 \(i\) 再乘上最大边在 \(m\) 条边中的排名为i的概率 \(P(i)\) 。也可以说是加入第 \(i\) 条边这个图刚好联通的概率。
就是：
这个式子和下面的式子等价。
\[ans=\frac{1}{m+1}\sum_{i=1}^{m}\sum_{j=i}^{m}P(j) \]考虑\(\sum_{j=i}^{n}P(j)\)是什么？其实就是加入 \(i-1\) 条边图不连通的概率。
所以问题转化为求加入 \(x\) 条边图不连通的概率。
然后这个概率显然等于加入x条边图不连通的方案数\(/\)总方案数。
因为总方案数好求就是\(C_m^x\)
所以问题又转化为加入 \(x\) 条边图不连通的方案数。
考虑用状压DP解决。
\(dp[i][j][0/1]\) 分别代表选了在点集 \(i\) 的生成子图中选了 \(j\) 条边不连通\(/\)连通的方案数。
\(dp[i][j][0]\) 套路求法，设定一个关键点，枚举关键点所在的连通子集 \(k\)，和子集 \(k\) 的生成子图中的边数 \(s\)，设 \(size[i]\)为点集 \(i\) 中的边的数量，转移方程为\(dp[i][j][0]=dp[k][s][1]*C_{size[i\ xor \ k]}^{j-s}\)。
利用\(dp[i][j][0]+dp[i][j][1]=C_{size[i]}^{j}\)就可以求出 \(dp[i][j][1]\) 。
最后
#include
#include
#include
#include
#include
using namespace std;
#define int long long
int dp[1111][111][2],n,m,u[111],v[111],C[111][111],size[1111];
double ans;
int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
signed main(){
n=read();m=read();
for(int i=1;i<=m;i++)u[i]=read(),v[i]=read();
for(int i=0;i<(1<