首页 > 代码库 > bzoj3925: [Zjoi2015]地震后的幻想乡
bzoj3925: [Zjoi2015]地震后的幻想乡
Description
傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有n个地方，那么最快的方法当然是修复n-1条道路将这n个地方都连接起来。 幻想乡这n个地方本来是连通的，一共有m条边。现在这m条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第i条边所需要的时间为ei。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个ei会是一个0到1之间均匀分布的随机实数。并且所有ei都是完全独立的。 现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那n-1条边，同时开始修复，那么修复完成的时间就是这n-1条边的ei的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边ei的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？
Input
第一行两个数n,m，表示地方的数量和边的数量。其中点从1到n标号。
接下来m行，每行两个数a,b，表示点a和点b之间原来有一条边。
这个图不会有重边和自环。
Output
一行输出答案，四舍五入保留6位小数。
假设边权分别为1/(m+1) 2/(m+1) ... m/(m+1)，答案不变
枚举集合划分，容斥处理出有几种可能的边的大小关系，使前k小的边恰好使图联通，然后可以统计答案
#include<cstdio>typedef long double ld;int n,m,c[1024],cs[16],mx;ld fac[107],fs[107],ans=0,C[107][107];int max(int a,int b){return a>b?a:b;}void dfs(int w,int mx){ if(w==n){ ld f[107]={}; f[0]=1; ld v=(mx-1&1)?-1:1; v*=fac[mx-1]; for(int t=0;t<mx;++t){ int k=c[cs[t]]; for(int i=m;i;--i){ for(int j=max(i-k,0);j<i;++j)f[i]+=f[j]*C[k][i-j]; } } for(int i=0;i<=m;++i)fs[i]+=f[i]*v; return; } for(int i=0;i<=mx;++i){ cs[i]^=1<<w; dfs(w+1,mx+(i==mx)); cs[i]^=1<<w; }}int main(){ scanf("%d%d",&n,&m); mx=1<<n; for(int i=fac[0]=1;i<=100;++i)fac[i]=fac[i-1]*i; C[0][0]=1; for(int i=0;i<=60;++i){ for(int j=0;j<=i;++j)C[i+1][j]+=C[i][j],C[i+1][j+1]+=C[i][j]; } for(int i=0,a,b;i<m;++i){ scanf("%d%d",&a,&b); --a,--b; for(int s=0;s<mx;++s)if(s>>a&s>>b&1)++c[s]; } dfs(0,0); for(int i=0;i<=m;++i)fs[i]*=fac[i]*fac[m-i]; for(int i=m;i;--i)fs[i]-=fs[i-1],ans+=fs[i]*i; ans/=fac[m+1]; printf("%.6f",(double)ans); return 0;}
bzoj3925: [Zjoi2015]地震后的幻想乡
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。