「ZJOI2015」地震后的幻想乡

客官°小女子只卖身不卖艺 2022-01-09 07:43 198阅读 0赞

## [ 传送门 ][Link 1] ##

## **Description**  ##

> 题目的**理解**方式：
> 
> 给定\\(n\\)个点，和\\(m\\)条边，每条边的期望完成时间都是一个\\(\[0,1\]\\)内的随机数
> 
> 求使得所有点都联通的期望时间
> 
> \\(n \\leq 10\\)

## **Solution**  ##

> 首先，对于\\(n\\)个\\(\[0,1\]\\)之间的随机变量\\(x\_1,x\_2,x\_3,...,x\_n\\)，第\\(k\\)小的那个数的期望值是\\(\\frac\{k\}\{n+1\}\\)
> 
> 所以，此题等价于是生成树的\\(n-1\\)条边中最后一个出现的边的期望排名
> 
> 假设这个排名为\\(i\\)的概率是\\(P(i)\\)
> 
> 那么：  
> \\\[ ans=\\frac\{1\}\{m+1\}\\sum\_\{i=1\}^\{m\}iP(i) \\\]  
> 我们再设\\(p(i)\\)表示最后一个出现的边排名\\(\\geq i\\)的概率
> 
> 原式转化为：  
> \\\[ \\sum\_\{i=1\}^\{m\}iP(i)=\\sum\_\{i=1\}^\{m\}p(i) \\\]  
> 然而事实上\\(p(i)\\)可以表示为加入\\(i-1\\)条边后原图不连通的概率
> 
> 设原图为\\(<V,E>\\),\\(V\\)为点集，\\(E\\)为边集  
> \\\[ p(i+1)=\\frac\{f\_\{i,V\}\}\{C(m,i)\} \\\]  
> 对于上面的式子，\\(f\_\{i,S\}\\)表示从\\(S\\)的生成子图中选出\\(i\\)条边，**不能**够使得点集联通的方案数
> 
> 再设\\(g\_\{i,S\}\\)表示从\\(S\\)的生成子图中选出\\(i\\)条边，**能**够使得点集联通的方案数
> 
> 对于集合\\(S\\)的生成子图\\(<S,E\_S>\\)  
> \\\[ f\_\{i,S\}+g\_\{i,S\}=C(|E\_S|,i) \\\]  
> 考虑转移，可以枚举当前集合中的一个点\\(x\\)所在的联通块以及这个联通块的边数  
> \\\[ f\_\{i,S\}=\\sum\_\{S' \\subset S,x\\in S'\}\\sum\_\{j=0\}^\{|E\_\{S'\}|\}g\_\{j,S'\}C(|E\_\{S-S'\}|,i-j) \\\]  
> 怎么求出边集的大小呢？
> 
> 首先求出每个点与某个集合的连边数量\\(Num\_\{i,S\}\\)
> 
> 对于一个集合\\(S\\)，\\(|E\_S|=|E\_\{S-x\}|+Num\_\{x,S-x\},x\\in S\\)
> 
> 然后，就没有然后啦
> 
> 组合数怎么算？目测会很大，用\\(double\\)存吧，写递推版
> 
> 因为有枚举子集，所以复杂度是\\(能过O(3^nm^2)=O(能过)\\)

## **Code ** ##

#include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)>(b)?(b):(a)) #define reg register using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } int N,M; bool mp[10][10]; int Num[10][1<<10],id[1<<10],E[1<<10]; double f[50][1<<11],g[50][1<<10]; double C[50][50],ans; double c(int x,int y){if(x<y)return 0.;return C[x][y];} int main() { N=read(),M=read(); reg int i,a,b,S=1<<N,s,j,sp; for(i=0;i<M;++i) a=read()-1,b=read()-1,mp[a][b]=mp[b][a]=true; for(i=0;i<N;++i) id[1<<i]=i; for(i=0;i<N;++i)for(j=1;j<S;++j) Num[i][j]=Num[i][j-(j&(-j))]+mp[i][id[j&(-j)]]; for(i=1;i<S;++i) E[i]=E[i-(i&(-i))]+Num[id[i&(-i)]][i-(i&(-i))]; C[0][0]=1.; for(i=1;i<=M;++i) { C[i][0]=C[i][i]=1.; for(j=1;j<i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1]; } for(i=0;i<S;++i) f[0][i]=1; for(i=0;i<N;++i) g[0][1<<i]=1,f[0][1<<i]=0; for(i=1;i<=M;++i)for(s=0;s<S;++s)if(i<=E[s]) { reg int x=id[s&(-s)]; for(sp=s-1;sp&=s;--sp)if(sp>>x&1)for(j=0;j<=i;++j) f[i][s]+=g[j][sp]*c(E[s-sp],i-j); g[i][s]=c(E[s],i)-f[i][s]; } for(i=1;i<=M;++i) ans+=f[i-1][S-1]/c(M,i-1); ans/=(double)M+1; printf("%.6lf\n",ans); return 0; }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/10659294.html

[Link 1]: https://loj.ac/problem/2136