洛谷3343 [zjoi2015]地震后的幻想乡

丽洁姐的毒瘤题

Posted by yjjr's blog on March 13, 2018

标签:DP,数学

题目

题目传送门

题目描述

傲娇少女幽香是一个很萌很萌的妹子,而且她非常非常地有爱心,很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不,幻想乡突然发生了地震,所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。

幻想乡一共有n个地方,那么最快的方法当然是修复n-1条道路将这n个地方都连接起来。 幻想乡这n个地方本来是连通的,一共有m条边。现在这m条边由于地震的关系,全部都毁坏掉了。每条边都有一个修复它需要花费的时间,第i条边所需要的时间为ei。地震发生以后,由于幽香是一位人生经验丰富,见得多了的长者,她根据以前的经验,知道每次地震以后,每个ei会是一个0到1之间均匀分布的随机实数。并且所有ei都是完全独立的。

现在幽香要出发去帮忙修复道路了,她可以使用一个神奇的大魔法,能够选择需要的那n-1条边,同时开始修复,那么修复完成的时间就是这n-1条边的ei的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边ei的值,然后再选择完成时间最小的方案。 幽香在走之前,她想知道修复完成的时间的期望是多少呢?

输入输出格式

输入格式

第一行两个数n,m,表示地方的数量和边的数量。其中点从1到n标号。 接下来m行,每行两个数a,b,表示点a和点b之间原来有一条边。 这个图不会有重边和自环。

输出格式

一行输出答案,四舍五入保留6位小数。

输入输出样例

输入样例#1

5 4
1 2
1 5
4 3
5 3

输出样例#1

0.800000

说明

提示

(以下内容与题意无关,对于解题也不是必要的。)

对于n个[0,1]之间的随机变量x1,x2,…,xn,第k小的那个的期望值是k/(n+1)。

样例解释

对于第一个样例,由于只有4条边,幽香显然只能选择这4条,那么答案就是4条边的ei中最大的数的期望,由提示中的内容,可知答案为0.8。

数据范围

对于所有数据:n<=10, m<=n(n-1)/2, n,m>=1。

对于15%的数据:n<=3。

另有15%的数据:n<=10, m=n。

另有10%的数据:n<=10, m=n(n-1)/2。

另有20%的数据:n<=5。

另有20%的数据:n<=8。

分析

题意:给定一个n个点m条边的无向图,无重边和自环,每条边的权值为[0,1]之间的随机变量,求最小生成树中最大边的期望权值

提示中根据期望的线性性,我们可以算出随机选出前k小的边使图联通的概率

e表示概率

因为精度问题,我们可以先算出可行方案数,再除以总方案数得到概率

  • cnt[i]表示点集i中的边数
  • f[i][j]表示点集为i,选用j条边使得点集不连通的方案数
  • g[i][j]表示点集为i,选用j条边使得点集连通的方案数

显然

对于计算f[S],令T为S的真子集且T和S-T之间不连通

那么就可以利用这个进行转移

最后的答案为(U表示全集)

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
	ll re=1;
	while(y){
	   	if(y&1)re=(re*x)%p;
		y>>=1,x=(x*x)%p;
	}
	return re;
}
//**********head by yjjr**********
const int maxn=16,maxm=46;
int n,m,e[maxn],sz[1<<maxn],cnt[1<<maxn];
ll c[maxm][maxm],f[1<<maxn][maxm],g[1<<maxn][maxm];
double ans;
int main()
{
	n=read(),m=read();
	rep(i,1,m){
		int u=read()-1,v=read()-1;
		e[u]|=1<<v;e[v]|=1<<u;
	}
	c[0][0]=1;
	rep(i,1,m){
		c[i][0]=c[i][i]=1;
		rep(j,1,i-1)c[i][j]=c[i-1][j-1]+c[i-1][j];
	}
	rep(S,1,1<<n){
		sz[S]=sz[S>>1]+(S&1);
		if(sz[S]==1){g[S][0]=1;continue;}
		rep(i,0,n-1)
			if((S>>i)&1)cnt[S]+=sz[e[i]&S];
		cnt[S]>>=1;
		for(int T=(S-1)&S;T;T=(T-1)&S)
			if(T&lowbit(S))
				rep(i,0,cnt[T])
					rep(j,0,cnt[S^T])
						f[S][i+j]+=g[T][i]*c[cnt[S^T]][j];
		rep(i,0,cnt[S])g[S][i]=c[cnt[S]][i]-f[S][i];
	}
	rep(i,0,m)ans+=(double)f[(1<<n)-1][i]/c[cnt[(1<<n)-1]][i];
	ans/=m+1;
	printf("%.6lf\n",ans);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr