标签：DP，数学
题目
题目描述
傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。
幻想乡一共有n个地方，那么最快的方法当然是修复n-1条道路将这n个地方都连接起来。 幻想乡这n个地方本来是连通的，一共有m条边。现在这m条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第i条边所需要的时间为ei。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个ei会是一个0到1之间均匀分布的随机实数。并且所有ei都是完全独立的。
现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那n-1条边，同时开始修复，那么修复完成的时间就是这n-1条边的ei的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边ei的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？
输入输出格式
输入格式
第一行两个数n,m，表示地方的数量和边的数量。其中点从1到n标号。 接下来m行，每行两个数a,b，表示点a和点b之间原来有一条边。 这个图不会有重边和自环。
输出格式
一行输出答案，四舍五入保留6位小数。
输入输出样例
输入样例#1
5 4
1 2
1 5
4 3
5 3
输出样例#1
0.800000
说明
提示
（以下内容与题意无关，对于解题也不是必要的。）
对于n个[0,1]之间的随机变量x1,x2,…,xn，第k小的那个的期望值是k/(n+1)。
样例解释
对于第一个样例，由于只有4条边，幽香显然只能选择这4条，那么答案就是4条边的ei中最大的数的期望，由提示中的内容，可知答案为0.8。
数据范围
对于所有数据：n<=10, m<=n(n-1)/2, n,m>=1。
对于15%的数据：n<=3。
另有15%的数据：n<=10, m=n。
另有10%的数据：n<=10, m=n(n-1)/2。
另有20%的数据：n<=5。
另有20%的数据：n<=8。
分析
题意：给定一个n个点m条边的无向图，无重边和自环，每条边的权值为[0,1]之间的随机变量，求最小生成树中最大边的期望权值
提示中根据期望的线性性，我们可以算出随机选出前k小的边使图联通的概率
\[ans=\frac {\sum e} {m+1}\]e表示概率
\[第k小的期望值为\frac k {m+1}\]因为精度问题，我们可以先算出可行方案数，再除以总方案数得到概率
令
- cnt[i]表示点集i中的边数
- f[i][j]表示点集为i,选用j条边使得点集不连通的方案数
- g[i][j]表示点集为i,选用j条边使得点集连通的方案数
显然
\[f[i][j] + g[i][j] = \binom{j}{cnt[i]}\]对于计算f[S]，令T为S的真子集且T和S-T之间不连通
\[f[S][i+j]=\sum_{T\subset S}{g[T][i]*\binom{j}{cnt[S-T]}}\]那么就可以利用这个进行转移
最后的答案为（U表示全集）
\[Ans=\frac{1}{m+1}\sum_{i=0}^{m}\frac{f[U][i]}{\binom{i}{cnt[U]}}\]code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
//**********head by yjjr**********
const int maxn=16,maxm=46;
int n,m,e[maxn],sz[1<<maxn],cnt[1<<maxn];
ll c[maxm][maxm],f[1<<maxn][maxm],g[1<<maxn][maxm];
double ans;
int main()
{
n=read(),m=read();
rep(i,1,m){
int u=read()-1,v=read()-1;
e[u]|=1<<v;e[v]|=1<<u;
}
c[0][0]=1;
rep(i,1,m){
c[i][0]=c[i][i]=1;
rep(j,1,i-1)c[i][j]=c[i-1][j-1]+c[i-1][j];
}
rep(S,1,1<<n){
sz[S]=sz[S>>1]+(S&1);
if(sz[S]==1){g[S][0]=1;continue;}
rep(i,0,n-1)
if((S>>i)&1)cnt[S]+=sz[e[i]&S];
cnt[S]>>=1;
for(int T=(S-1)&S;T;T=(T-1)&S)
if(T&lowbit(S))
rep(i,0,cnt[T])
rep(j,0,cnt[S^T])
f[S][i+j]+=g[T][i]*c[cnt[S^T]][j];
rep(i,0,cnt[S])g[S][i]=c[cnt[S]][i]-f[S][i];
}
rep(i,0,m)ans+=(double)f[(1<<n)-1][i]/c[cnt[(1<<n)-1]][i];
ans/=m+1;
printf("%.6lf\n",ans);
return 0;
}
