Description

给出无向图G(V, E). 每次操作任意加一条非自环的边(u, v), 每条边的选择是等概率的. 问使得G连通的期望操作次数. (|V| <= 30, |E| <= 1000)
Input

第一行两个整数N,M 1<=N<=30 0<=M<=1000 接下来M行,每行两个整数X,Y表示两者之间已修好一条道路. 两点之间可以不止修了一条路,也有可能M条路已使N个点成为一个整体.
Output

输出一个小数,表示新修道路条数的期望值,保留六位小数.
Sample Input
4 2

1 2

3 4

Sample Output
1.500000

　给出N个点M条边，每次等概率的给这张图加一条边，求连通这个图加边次数的期望。
　
这题我们并不关心图的形状，只要知道图的连通情况即可，即这张图有几个连通块，每个连通块中有几个顶点。比

如，我们用E(2,3,3)表示当这个图有3个连通块，每个连通块中的顶点数分别是2,3,3时，我们把它连通所需加边的期望，

对于8个顶点的图，E(8)=0。可以得到转移方程

E(2,3,3)=p1*E(2,3,3)+p2*E(2,6)+p3*E(3,5)+1。

把右边的第一项移到左边，然后用记忆化搜索就可以求解了。

其中p1,p2,p3是转移到其它连通情况的概率，在8个点里连一条边，总的方案数显然是C(8,2)。如果这条边没有改变连

通情况，说明连的是同一个连通块里的边，于是p1=(C(2,2)+C(3,2)+C(3,2))/C(8,2)。否则就是在两个连通块里各选了一

条边，枚举可以得到p2=(3*3)/C(8,2)，p3=(2*3+2*3)/C(8,2)。

对图的每种状态先排个序，然后用HASH即可。

///BZOJ 1417

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define ll long long
#define vec vector<int>
const int maxn = 100;

map<vec, double>mp;
vec ve;
int fa[maxn], siz[maxn], all, n, m;
int find_set(int x){
    if(x==fa[x]) return x;
    else return fa[x]=find_set(fa[x]);
}
void init(){
    scanf("%d%d", &n,&m);
    for(int i=1; i<=n; i++) fa[i]=i,siz[i]=1;
    for(int i=1; i<=m; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        int fx = find_set(u), fy = find_set(v);
        if(fx!=fy) fa[fx]=fy,siz[fy]+=siz[fx];
    }
    for(int i=1; i<=n; i++) if(i==fa[i]) ve.push_back(siz[i]);
    sort(ve.begin(),ve.end());
    all = n*(n-1)/2;
}

double DP(vec ve)
{
    if(mp.count(ve)) return mp[ve];
    if(ve.size()==1) return mp[ve]=0;
    int sz=ve.size();
    int p=0;
    for(int i=0; i<sz; i++){
        p+=ve[i]*(ve[i]-1)/2;
    }
    double ans=1.0*all/(all-p);
    for(int i=0; i<sz; i++){
        for(int j=0; j<i; j++){
            vec v=ve;
            v[j]+=v[i];
            swap(v[i], v[sz-1]);
            v.pop_back();
            sort(v.begin(),v.end());
            ans+=1.0*ve[i]*ve[j]/(all-p)*DP(v);
        }
    }
    return mp[ve]=ans;
}

int main()
{
    init();
    printf("%.6f\n", DP(ve));
    return 0;
}