【BZOJ1417】Pku3156 Interconnect

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

题解：思路非常巧妙。

因为30的整数划分只有几千种，所以我们可以将每个连通块的大小设为状态，排序后用vector+map存起来，然后进行DP（其实应该用hash的，交到poj上TLE了）。

DP时枚举连接的是哪两个连通块，也有可能连接的是同一个连通块，简单推一推算一算就好。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

#include <map>

#include <algorithm>

using namespace std;

typedef vector<int> vec;

map<vec,double> g;

int n,m;

int f[35],siz[35];

double DP(vec v)

{

	if(v.size()==1)	return 0;

	if(g.find(v)!=g.end())	return g[v];

	vec::iterator i,j,k;

	double gv=0,tmp=n*(n-1)/2;

	for(i=v.begin();i!=v.end();i++)	tmp-=(*i)*((*i)-1)/2;

	for(i=v.begin();i!=v.end();i++)

	{

		for(j=i,j++;j!=v.end();j++)

		{

			vec t;

			for(k=v.begin();k!=v.end();k++)	if(k!=i&&k!=j)	t.push_back(*k);

			t.push_back((*i)+(*j));

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

			gv+=DP(t)*(*i)*(*j)/tmp;

		}

	}

	return g[v]=n*(n-1)/2/tmp+gv;

}

int find(int x)

{

	return (f[x]==x)?x:(f[x]=find(f[x]));

}

int main()

{

	scanf("%d%d",&n,&m);

	int i,a,b;

	for(i=1;i<=n;i++)	f[i]=i,siz[i]=1;

	for(i=1;i<=m;i++)

	{

		scanf("%d%d",&a,&b),a=find(a),b=find(b);

		if(a!=b)	siz[b]+=siz[a],f[a]=b;

	}

	vec v;

	for(i=1;i<=n;i++)	if(find(i)==i)	v.push_back(siz[i]);

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

	printf("%.6lf",DP(v));

	return 0;

}

秒客网

【BZOJ1417】Pku3156 Interconnect 记忆化搜索