Interconnect Interconnect

Time Limit:10000MS  Memory Limit:65536K
Total Submit:48 Accepted:37
Case Time Limit:1000MS

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

Source
这个题目我看到之后第一感觉就是状态压缩Dp。。
状态就是各个联通块的大小。。
然后发现状态最多只有5604个。。
然后就可以无压力Dp了。。
为了方便我使用了Map存数据，vector存状态，
速度奇慢无比。。

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(VI::iterator e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1;
using namespace std;
typedef vector<int> VI;
map<VI,double> Map;
int n,m;
int total;
double Dp(VI A)
{
if(Map.count(A))return Map[A];
double&x=Map[A];
if(A.size()==1)return x=0;
double same=0;
rep(i,A.size())
rep(j,i+1)
if(i==j)
same+=double(A[i]*(A[i]-1)/2)/total;
else
{
VI New=A;
New[i]+=New[j];swap(New[j],New[New.size()-1]);
New.pop_back();sort(New.begin(),New.end());
x+=double(A[i]*A[j])/total*Dp(New);
}
x=(x+1)/(1-same);
return x;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;total=n*(n-1)/2;
VI comp(n);
rep(i,n)comp[i]=i;
int s,t;
rep(i,m)
{
cin>>s>>t;–s;–t;int that=comp[t];
if(comp[s]!=comp[t])
rep(j,n)if(comp[j]==that)
comp[j]=comp[s];
}
VI count(n,0),Now;
rep(i,n)count[comp[i]]++;
rep(i,n)if(count[i])Now.pb(count[i]);
sort(Now.begin(),Now.end());
printf("%0.6lfn",Dp(Now));
//cout<<Map.size()<<endl;
}