Description
给定一张$n$个顶点$n$条边图,定义过程$solve(G),G$是一个连通块.
$1.totalCost=totalCost+|G|,|G|$表示图$G$中的节点个数.
$2.$在图$G$中随机选择一个节点$x$(每个点被选中的概率相等).
$3.$在图$G$中删除节点$x$.
$4.$图被分裂为几个连通块.
$5.$分治处理所有的子连通块$G‘,solve(G‘)$.
求$totalCost$的数学期望.
Input
第一行一个整数$n$,表示图中点的数量和边的数量.
接下来$n$行,每行两个空格隔开的整数$a_i,b_i$,表示一条$(a_i,b_i)$的无向边.
节点从$0$开始编号.
Output
仅一行输出一个实数,表示$totalCost$的数学期望.和标准答案绝对误差或相对误差在$10^{?6}$以内都被认为正确.
Sample Input
5
3 4
2 3
2 4
0 4
1 2
Sample Output
13.1666666666
HINT
$n\;\leq\;3000$
Solution
定义事件$P(A,B)$为在删除点$A$时,$B$点仍与$A$点连通的概率.
显然当一个事件发生时,答案$+1$,所以答案的期望值为所有事件的总和.
$P(A,B)=$在$AB$路径上的点数的倒数.
设$AB$路径上的点数为$n$.
- 当连通块大小$=n$时,连通块为链$AB$.只有选取$A$时才会发生事件$P(A,B)$,概率为$\frac{1}{n}$.
- 当连通块大小$\geq\;n$,为$x$时,选取的点有两种情况:
- 选取在$AB$链上,这时的概率为$\frac{n}{x}\times\frac{1}{n}$;
- 选取不在$AB$链上,概率为$\frac{x-n}{x}\times\frac{1}{n}$.
- 相加为$\frac{1}{n}$.
- $AB$间的路径没通过环,结论同树.
- $AB$间的路径经过了环,可以将路径上的点分成三部分:
- 环外的点$x$,数量记为$X$.
- 环上$A$到$B$顺时针的点$y$,数量记为$Y$.
- 环上$B$到$A$顺时针的点$z$,数量记为$Z$.
- 在选取$A$之前,$y,z$之间必须有一条不能被取,不能选取$x$.期望值为$\frac{1}{X+Y}+\frac{1}{X+Z}-\frac{1}{X+Y+Z}$.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 3005 using namespace std; struct graph{ int nxt,to; }e[N<<1]; int g[N],t[N],d1[N],d2[N],n,cnt; bool ins[N]; double ans; queue<int> q; inline int read(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1)+(ret<<3)+c-‘0‘; c=getchar(); } return ret; } inline void addedge(int x,int y){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y; } inline void toposort(){ int u; for(int i=1;i<=n;++i) if(t[i]==1) q.push(i); while(!q.empty()){ u=q.front();q.pop();++cnt; for(int i=g[u];i;i=e[i].nxt) if((--t[e[i].to]==1)) q.push(e[i].to); } } inline void dfs(int u){ ins[u]=true; for(int i=g[u];i;i=e[i].nxt) if(!ins[e[i].to]){ d2[e[i].to]=d2[u]+1; if(!d1[e[i].to]){ d1[e[i].to]=d1[u]+1; ans+=1.0/(double)(d1[e[i].to]); } else ans+=1.0/(double)(d2[e[i].to])-2.0/(double)(d1[e[i].to]+d2[e[i].to]+cnt-2); dfs(e[i].to); } ins[u]=false; } inline void Aireen(){ n=read(); for(int i=1,j,k;i<=n;++i){ j=read()+1;k=read()+1; addedge(j,k);addedge(k,j); ++t[j];++t[k]; } cnt=0;toposort();cnt=n-cnt; for(int i=1;i<=n;++i){ memset(d1,0,sizeof(d1)); memset(d2,0,sizeof(d2)); d1[i]=d2[i]=1;dfs(i); } printf("%.8lf\n",ans+n); } int main(){ freopen("dac.in","r",stdin); freopen("dac.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0; }
原文：http://www.cnblogs.com/AireenYe/p/6269190.html