bzoj1417: Pku3156 Interconnect

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1417

1417: Pku3156 Interconnect

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 257 Solved: 133
[Submit][Status][Discuss]

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

HINT

Source

我们发现每个点都是一样的，对答案有影响的是联通块的数量。每次加边只有两种情况：联通块个数不变或-1 。所以我们可以dp，E[S]=ΣΣ|C[i]|*|C[j]|/(all-p)*E[S']+all/(all-p)，每次把dp出的答案放到map或者hash里就好了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<vector>
 5 #include<map>
 6 #include<algorithm>
 7 using namespace std;
 8 int n,m,all,fa[35],size[35];
 9 typedef vector<int> pps;
10 pps v;
11 map<pps,double>fuckp;
12 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
13 double calc(pps ve){
14     if(fuckp.count(ve))return fuckp[ve];
15     if(ve.size()==1)return fuckp[ve]=0;
16     int s=ve.size();double ss=0;
17     for(int i=0;i<s;i++)ss+=ve[i]*(ve[i]-1)/2;
18     double p=1.0*all/(all-ss);
19     for(int i=0;i<s;i++)
20     for(int j=0;j<i;j++){
21         pps b=ve;b[j]+=b[i];swap(b[i],b[s-1]);
22         b.pop_back();sort(b.begin(),b.end());
23         p+=1.0*ve[i]*ve[j]/(all-ss)*calc(b);
24     }
25     return fuckp[ve]=p;
26 }
27 int main(){
28     scanf("%d%d",&n,&m);all=(n-1)*n/2;
29     for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;
30     for(int i=1;i<=m;i++){
31         int x,y;
32         scanf("%d%d",&x,&y);
33         x=find(x);y=find(y);if(x!=y)fa[x]=y,size[y]+=size[x];
34     }
35     for(int i=1;i<=n;i++)if(fa[i]==i)v.push_back(size[i]);
36     sort(v.begin(),v.end());
37     printf("%.6lf
",calc(v));
38     return 0;
39 }

View Code