bzoj1417: Pku3156 Interconnect

2023-02-23 18:08:54

题目链接：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里就好了。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<algorithm>

 using namespace std;

 int n,m,all,fa[],size[];

 typedef vector<int> pps;

 pps v;

 map<pps,double>fuckp;

 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

 double calc(pps ve){

     if(fuckp.count(ve))return fuckp[ve];

     if(ve.size()==)return fuckp[ve]=;

     int s=ve.size();double ss=;

     for(int i=;i<s;i++)ss+=ve[i]*(ve[i]-)/;

     double p=1.0*all/(all-ss);

     for(int i=;i<s;i++)

     for(int j=;j<i;j++){

         pps b=ve;b[j]+=b[i];swap(b[i],b[s-]);

         b.pop_back();sort(b.begin(),b.end());

         p+=1.0*ve[i]*ve[j]/(all-ss)*calc(b);

     }

     return fuckp[ve]=p;

 }

 int main(){

     scanf("%d%d",&n,&m);all=(n-)*n/;

     for(int i=;i<=n;i++)fa[i]=i,size[i]=;

     for(int i=;i<=m;i++){

         int x,y;

         scanf("%d%d",&x,&y);

         x=find(x);y=find(y);if(x!=y)fa[x]=y,size[y]+=size[x];

     }

     for(int i=;i<=n;i++)if(fa[i]==i)v.push_back(size[i]);

     sort(v.begin(),v.end());

     printf("%.6lf\n",calc(v));

     return ;

 }

码农公寓