题目大意：给定一张点数不超过10的无向连通图，每条边有一个[0,1]之间的随机权值，，求最小生成树上最大边的期望值
此生无悔入东方，来世愿生幻想乡
OTZ
首先既然权值在[0,1]之间均匀分布那么两条边权值相同的概率为0 于是我们只考虑所有边边权都不同的情况
如果最小生成树上的最大边为x，那么权值小于x的边一定不能将这个图连通，而权值<=x的边就可以
因此对于一个x，如果我们求出【只有边权小于x的边存在时这个图不连通】的概率，那么这个概率就是答案>=x的概率
不妨设这个概率为f(x) 那么这个f(x)其实是关于x的一个多项式 而答案就是∫[0,1]f(x)dx
至于为什么答案是f(x)的积分可以感性理解下。。。我数死早。。。
下面就是如何求f(x)了
首先【边权小于x的概率】就是x 因此这个问题等价于【每条边有x的概率出现时这个图不连通的概率】
”然后就是经典做法了“。。。clj只说到这。。。然后我扒了半天代码才反应过来怎么做QAQ 我好弱QAQ
这个做法和POJ1737 连通图的做法是类似的
首先我们考虑补集法 求这个图连通的概率 然后用1减掉就行了
然后我们枚举每一个诱导子图 计算这个子图连通的概率
首先我们任选子图中的一点p，然后枚举哪些点与p相连
设p所在联通块联通的概率为q，x所在联通块与其它点之间共有k条边，那么这种情况不连通的概率就是q*(1-x)^k
从1中减掉所有不连通的概率就是这个状态连通的概率了。。。
我语死早看不懂就去看代码吧。。。。
注意精度有问题 long double过不去 要用__float128
#include <vector>#include <cstdio>#include <cstring>#include <iomanip>#include <iostream>#include <algorithm>#define M 15using namespace std; typedef __float128 ld;typedef vector<long long> Poly; int n,m,a[M]; Poly pow_1_x[M*M],f[1<<10]; Poly operator + (const Poly &x,const Poly &y){int i;Poly re(max(x.size(),y.size()),0);for(i=0;i<x.size();i++)re[i]+=x[i];for(i=0;i<y.size();i++)re[i]+=y[i];return re;} Poly operator – (const Poly &x,const Poly &y){int i;Poly re(max(x.size(),y.size()),0);for(i=0;i<x.size();i++)re[i]+=x[i];for(i=0;i<y.size();i++)re[i]-=y[i];return re;} Poly operator * (const Poly &x,const Poly &y){int i,j;Poly re(x.size()+y.size()-1,0);for(i=0;i<x.size();i++)for(j=0;j<y.size();j++)re[i+j]+=x[i]*y[j];return re;} ld Integrate (const Poly &x){int i;ld re=0;for(i=0;i<x.size();i++)re+=(ld)x[i]/(i+1);return re;} int Count(int x){int re=0;for(;x;x-=x&-x)re++;return re;} int main(){int i,j,k,x,y;cin>>n>>m;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);a[x]|=1<<y-1;a[y]|=1<<x-1;}new (&pow_1_x[0])Poly(1,1);new (&pow_1_x[1])Poly(2,0);pow_1_x[1][0]=1;pow_1_x[1][1]=-1;for(i=2;i<=m;i++)pow_1_x[i]=pow_1_x[i-1]*pow_1_x[1];for(i=1;i<1<<n;i++){new (&f[i])Poly(1,1);for(x=1;x<=n;x++)if(i>>x-1&1)break;for(j=i^(1<<x-1);j;(–j)&=i^(1<<x-1)){int temp=i^j,cnt=0;for(k=1;k<=n;k++)if(temp>>k-1&1)cnt+=Count(a[k]&j);f[i]=f[i]-f[temp]*pow_1_x[cnt];}}Poly disconnect=Poly(1,1)-f[(1<<n)-1];ld ans=Integrate(disconnect);cout<<fixed<<setprecision(6)<<(double)ans<<endl;return 0;}
美好的生命应该充满期待、惊喜和感激
