题意：给一个图，有些点之间已经连边，现在给每对点之间加边的概率是相同的，问使得整个图连通，加边条数的期望是多少。
此题可以用概率DP+并查集+hash来做。
用dp（i，j，k...)表示当前的每个联通分量的点数分别是i，j，k...（连通分量的个数不固定）时，加边的期望。
这样以dp（i，j，k)为例分析状态转移的过程，dp（i，j，k)=p1*dp（i，j，k)+p2*dp（i+j，k)+p3*dp（i，j+k)+p4*dp(j,i+k)+1。
终止条件是dp（n）=0，因为此时图一定联通，所以期望是0。
这个式子是怎么来的呢？
p1*dp（i，j，k)表示增加了一条边之后原来的联通分量没有改变时的情况，p1表示选中这样的无用边的概率；p2*dp（i+j，k)表示增加了一条连结i和j这两个联通分量的边，p2表示选中i和j之间的边的概率。最后的1表示增加了一条边。
这里我们要计算选边概率。
首先有n*（n-1）/2条边。
如果选中了不改变图的联通分量的边，此时说明每次加的边都属于一个连通分量，所以一共有sum{(cnt(i)*cnt(i)-1)/2}（cnt(i)表示该联通分量内有cnt(i)个点）种选择情况。
如果选中了某条边连结了某两个联通分量i、j，这个时候一共有cnt（i）*cnt（j）种情况。
计算概率只需要除以边的总数即可。
计算连通分量可以用并查集。
因为这个题只看图的连通情况不在乎具体是哪个点，因此可以对每个联通分量的点数排序，使得每个状态唯一，这样可以得到很多重叠的子问题，整个问题就可以用记忆化搜索完成了。
很明显问题的状态比较复杂，直接下手很难处理也容易超时，所以用hash处理状态压缩判重。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define MOD 100007
using namespace std;
int n,m;
struct State
{
double val;
];
bool vis;
State()
{
memset(x,,sizeof(x));
vis=false;
}
void clear()
{
memset(x,,sizeof(x));
vis=false;
}
void mysort()
{
sort(x,x+);
}
int myhash() const
{
;
,b=; i>=&&x[i]; --i)
{
res+=x[i]*b;
res%=MOD;
b*=;
b%=MOD;
}
return res;
}
bool operator ==(State &t)const
{
; i<; ++i) if(x[i]!=t.x[i]) return false;
return true;
}
bool operator !=(State &t) const
{
return !(*this==t);
}
};
State has[MOD+],st;
void inserthash(State &p)
{
int v=p.myhash();
while(has[v].vis)
;
has[v]=p;
has[v].vis=true;
}
double gethash(State &p)
{
int v=p.myhash();
while(has[v].vis&&has[v]!=p)
;
;
}
];
int find(int p)
{
return p==father[p]?p:(father[p]=find(father[p]));
}
void init()
{
; i<=n; ++i) father[i]=i;
st.clear();
}
double DP(State &s)
{
;
double v=gethash(s);
if(v!=-1.0) return v;
,sn=n*(n-)/2.0;;
; i>=&&s.x[i]; --i)
q+=s.x[i]*(s.x[i]-)/2.0;
double &res=s.val;
res=;
; i>=&&s.x[i]; --i)
; j>=&&s.x[j]; --j)
{
double p=s.x[i]*s.x[j]/sn;
State t;
; k>=; --k)
if(k!=i&&k!=j) t.x[k]=s.x[k];
else if(k==i) t.x[k]=s.x[i]+s.x[j];
;
t.mysort();
res+=p*DP(t);
}
res=res/(-q/sn);
inserthash(s);
return res;
}
];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
; i<m; ++i)
{
int x,y;
scanf("%d%d",&x,&y);
int fx=find(x),fy=find(y);
if(fx!=fy) father[fx]=fy;
}
memset(cnt,,sizeof(cnt));
; i<=n; ++i)
cnt[find(i)]++;
; i<=n; ++i)
st.x[i-]=cnt[i];
st.mysort();
printf("%.6f\n",DP(st));
}
;
}
学习了http://www.cnblogs.com/swm8023/archive/2012/09/21/2696593.html。