题目：https://www.luogu.org/problemnew/show/P3343
1.那个时间与边的大小排名有关，所以需要求一下最大边的期望排名就行。
2.期望排名是这样算的：(排名为1的概率 * 1(1的值) + 排名为2的概率 * 2 + ……) / (m+1)
仔细一想可以变成这样：(排名>=1的概率 + 排名>=2的概率 + ……) / (m+1)
可以是这样？——(连0时不能联通的概率 + 连1时不能联通的概率 + ……) / (m+1)
这里的0、1等可以看作是“前几条边”,也就是“几条边”；
3.这些概率不用每一步都就是概率，可以算的是方案、最后再除以所有方案数；
这个“几条边”的方案可以用dp来推（只要注意转移到它的状态里的边不重复）！状压记录点集。
发现 用了 i 条边不连通的方案数 + 用了 i 条边连通的方案数 = 从m条边里选 i 条边的方案数，所以求出一个就能算出另一个了。
如果求“用了 i 条边连通的方案数”，每一种情况由三部分构成：一条边和这条边两边的两个点集；
我们需要枚举一条被选的边，再枚举一个端点的点集，剩下的点构成另一个点集，这两个点集的“连通”方案数相乘(还要枚举其中一个点集用了多少条边)。
但状态里记录的是点集，要枚举那条边有点麻烦。
如果求“用了 i 条边不连通的方案数”，每一种情况就只由两个点集转移来，无需有中间那条边；
枚举这两个点集时为了不重不漏，可以确定一个“划分点”，枚举的那个点集必须包含它，并限制枚举的这个点集是连通的；然后剩下的点随便连边(组合数)。
(2018.6.16 PS:这个点必须被限制在一个连通块里。不能把它限制在随便的那个部分里，会重复。一条边也没有的图就是一个例子。)
4.代码里：组合数的赋初值！别忘了zh[0][0]！！还应注意一些地方从0或从1开始。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,dp[][][(<<)+],lm;
int siz[(<<)+],zh[][];
int head[],num[<<],pre[];
double ans;
bool vis[],in[],ed[];
struct Edge{
int next,to;
Edge(int n=,int t=):next(n),to(t) {}
}edge[];
int dfs(int cur)
{
vis[cur]=;int ret=;
for(int i=head[cur],v;i;i=edge[i].next)
if(in[v=edge[i].to])
{
if(!ed[i])ret++,ed[i]=;
if(!vis[v])ret+=dfs(v);
}
return ret;
}
void init()
{
lm=(<<n);
for(int i=;i<=n;i++)num[<<(i-)]=i;
for(int i=;i<lm;i++)
{
int k=i;
memset(ed,,sizeof ed);memset(vis,,sizeof vis);
memset(in,,sizeof in);
while(k)in[num[k&(-k)]]=,k-=(k&(-k));
for(int j=;j<=n;j++)if(in[j])siz[i]+=dfs(j);siz[i]>>=;
}
zh[][]=;//!!!!!!!
for(int i=;i<=m;i++)
{
zh[][i]=;
for(int j=;j<i;j++)
zh[j][i]=zh[j][i-]+zh[j-][i-];
zh[i][i]=;
}
for(int i=;i<lm;i++)dp[][][i]=;
for(int i=;i<=n;i++)dp[][][<<(i-)]=,dp[][][<<(i-)]=;
}
int main()
{
// freopen("zjsc.out","w",stdout);
scanf("%d%d",&n,&m);int u,v;
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
edge[i]=Edge(head[u],v);head[u]=i;
edge[i+m]=Edge(head[v],u);head[v]=i+m;
// dp[1][1][(1<<(u-1))|(1<<(v-1))]=1;
}
init();
// for(int i=1;i<lm;i++)if(!dp[1][1][i])dp[0][1][i]=1;
for(int i=;i<=m;i++)
for(int s=;s<lm;s++)
{
int k=;for(;(s&(<<(k-)))==;k++);
for(int c=((s-)&s);c;c=((c-)&s))
if(c&(<<(k-)))
{
// if(i==1)printf("s=%d c=%d\n",s,c);
for(int j=;j<=i;j++)//0~i
{
// if(i==1&&j==1)printf(" dp1=%d\n",dp[1][j][c]);
dp[][i][s]+=dp[][j][c]*zh[i-j][siz[s^c]];
// if(i==1&&s==7&&c==5)
// printf("j=%d dp1jc=%d zh=%d dp0is=%d\n",
// j,dp[1][j][c],zh[i-j][siz[s^c]],dp[0][i][s]);
// if(i==1&&dp[0][i][s])printf("j=%d s=%d dp0=%d\n",j,s,dp[0][i][s]);
}
}
dp[][i][s]=zh[i][siz[s]]-dp[][i][s];
// if(i==1)printf("(s=%d dp1=%d)\n",s,dp[1][i][s]);
}
// for(int i=1;i<=n;i++)
// {
// pre[i]=dp[0][i-1][lm-1]-dp[0][i][lm-1];
// pre[i]/=zh[i][n];
// }
// for(int i=1;i<=n;i++)
// ans+=(double)i/(n+1)*pre[i];
for(int i=;i<m;i++)ans+=(double)dp[][i][lm-]/(double)zh[i][m];//其实是<m,但dp[0][m][lm-1]肯定是0
printf("%.6lf",(double)ans/(double)(m+));//已求者为排名期望
return ;
}