题解 P3343 【[ZJOI2015]地震后的幻想乡】

ButterflyDew

2019-03-05 15:13:19

Solution

想了半天,打开洛谷题解一看,最高票是_rqy的,一堆密密麻麻的积分差点把我吓跑。 据说有三种解法,然而我只学会了一种最辣鸡的凡人解法。 upt:更正了一些错误.. ------ 题意:给一个无向图$G$,边权为$[0,1]$间的实数,求这个图的最小生成树的最大边权期望。 提示:对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,\dots,x_n$,第 $k$ 小的那个的期望值是 $\frac{k}{n+1}$。 ------ 考虑使用这个提示来帮助解题。 首先有一个暴力做法,枚举边权的相对大小,然后做最小生成树,kruskal得到一棵树时拿提示算一下 这个想法启发我们钦定一个边集$S$作为前$|S|$小,如果这个边集加入第$|S|$小这条边时恰好使图联通,我们就可以算它的贡献是$\frac{|S|}{m+1}$,如果我们还能算出它的方案并除上总方案,我们就可以得到它的概率,所以考虑去统计这个方案。 恰好联通这个条件并不好统计,我们转换一下,可以变成 `恰好联通方案=加之前不连通方案-加之后不连通方案` 然后比较自然的可以考虑压一个子集去做$dp$ 令$f_{S,i},g_{S,i}$分别表示点集为$S$,用了$i$条边,且点集不联通/连通的方案数,设$d_S$为点集$s$在图$G$中的边数 显然有 $$g_{S,i}+f_{S,i}=\binom{d_S}{i}$$ 考虑$f$的递推,我们枚举$s$的子集,并且**钦定**某个点$k$一定在子集里,有转移 $$f_{S,i}=\sum_{k\in T\subset S}\sum_{j=0}^{d_T}g_{T,j}\binom{d_{S-T}}{i-j}$$ 然后最后考虑如何统计答案,设$U$为全集,按照之前说的,答案为 $$\sum_{k=1}^{m+1}\frac{k}{m+1}\times (\frac{f_{U,k-1}}{\binom{d_u}{k-1}}-\frac{f_{U,k}}{\binom{d_u}{k}})$$ 化简一下 $$\frac{1}{m+1}\sum_{k=1}^m\frac{f_{U,k}}{\binom{d_U}{k}}$$ ------ **Code:** ```cpp #include <cstdio> #include <cctype> #include <algorithm> using std::min; template <class T> void read(T &x) { x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-'0',c=getchar(); } double C[51][51],f[1<<10][51],g[1<<10][51]; int yuu[1<<10],dew[1<<10],n,m; int main() { read(n),read(m); for(int u,v,i=1;i<=m;i++) { read(u),read(v); ++dew[(1<<u-1)|(1<<v-1)]; } for(int s=1;s<1<<n;s++) for(int t=s;t;t=t-1&s) yuu[s]+=dew[t]; C[0][0]=1; for(int i=1;i<=m;i++) { C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1]; } for(int s=1;s<1<<n;s++) { for(int i=0;i<=yuu[s];i++) { for(int t=s-1&s;t;t=t-1&s) if(t&(s&-s)) for(int j=0;j<=min(i,yuu[t]);j++) f[s][i]+=g[t][j]*C[yuu[s^t]][i-j]; g[s][i]=C[yuu[s]][i]-f[s][i]; } } double ans=0; for(int i=0;i<=m;i++) ans+=f[(1<<n)-1][i]/C[m][i]; ans/=m+1.0; printf("%.6f\n",ans); return 0; } ```