[ZJOI2015]地震后的幻想乡

description

给定一个(n)个节点(m)条边的无向图,其中每条边的权值在([0,1])内均匀随机,
求最小生成树最大边权的期望。
(nle 10,mle frac{n(n-1)}{2})

solution

这题有两种做法。

orz _rqy

由于边权的期望

[egin{aligned} E(X)&=int_0^1P(X=x)xdx\ &=int_0^1P(X=x)int_0^xdtdx\ &=int_0^1(int_t^1P(X=x)dx)dt\ &=int_0^1P(Xge t)dt\ end{aligned} $$故考虑边权的概率生成函数$F(x)=int_0^1P(xge t)dt$。设$P_S(t)$为$S$内的节点通过$<t$的边不能连通的概率,通过子集容斥可得转移方程为 $$int_0^1P_S(t)dt=int_0^1sum_{S_0subsetneq S,pin S_0}(1-t)^{T(S_0,S-S_0)}(1-P_{S_0}(t))dt$$其中$p$为点集$S$内确定的一点。转化得 ]

egin{aligned}
int_0^{1P_S(t)dt&=int_0}1sum_{S_0subsetneq S,pin S_0}(1-t)^{T(S_0,S-S_0)}(1-P_{S_0}(t))dt
&=sum_{S_0subsetneq S,pin S_0}int_0^1(1-t){T(S_0,S-S_0)}(1-P_{S_0}(t))dt
&=sum_{S_0subsetneq S,pin S_0}int_0^1(1-t){T(S_0,S-S_0)}-(1-t)^{T(S_0,S-S_0)}P_{S_0}(t)dt
&=sum_{S_0subsetneq S,pin S_0}frac{1}{1+T(S_0,S-S_0)}-int_0^1(1-t){T(S_0,S-S_0)}P_{S_0}(t)dt
end{aligned}

[于是有 $$int_0^1(1-t)^kP_S(t)dt=sum_{S_0subsetneq S,pin S_0}frac{1}{1+k+T(S_0,S-S_0)}-int_0^1(1-t)^{k+T(S_0,S-S_0)}P_{S_0}(t)dt]

记录(S,k),直接一路推到答案即可。

orz shadowice1984

首先如果我们枚举(m)条边的大小关系((O(m!))种)很显然这(m!)中关系出现的概率都是相等的
那么我们就有了一个(O(mm!))的暴力做法:
知道了边的大小关系,我们就可以知道最小生成树的最大边的排名了,然后直接套用给出的公式即可

现在考虑子集dp,设(f[S][k])表示在点集(S)内最小生成树的最大边排名为(k)的概率

发现这个没法转移,考虑将这个条件转化为在S内连了k条边后连通的方案数
转移有$$f[S][k]=inom{A[S]}{k}-sum_{S_0subsetneq S,pin S_0}sum_{i=0}^kf[S_0][i]inom{A[S-S_0]}{k-i}$$其中(A[S])表示(S)内的边数。

但我们发现求出来(WA)了。
重新考虑一下,在S内连了k条边后连通的方案数应该是点集(S)内最小生成树的最大边排名小于等于(k)的概率

所以利用之前的公式,(E=sum_{i=1}^{m}P(x=i)i=sum_{i=1}^{m}P(xge i)=sum_{i=1}^{m}1-P(xle i-1))

然后就可以做了。

Code

#include<bits/stdc++.h>
#define FL "a"
using namespace std;
typedef long long ll;
typedef double dd;
const int N=52;
const int mod=997;
const dd eps=1e-9;
inline ll read(){
  ll data=0,w=1;char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  if(ch=='-')w=-1,ch=getchar();
  while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
  return data*w;
}
inline void file(){
  freopen(FL".in","r",stdin);
  freopen(FL".out","w",stdout);
}

int n,m,A[1<<10],cnt[1<<10],low[1<<10];
dd c[N][N],ans,dp[1<<10][N];
void print(int s,int k){if(k)print(s>>1,k-1),putchar(48+(s&1));}
dd dfs(int s,int k){
  if(dp[s][k]>=0)return dp[s][k];
  if(cnt[s]==1&&!k)return 1;if(A[s]<k)return 0;
  dd &res=dp[s][k];res=c[A[s]][k];
  for(int i=k;~i;i--)
    for(int t=(s-1)&s;t;t=(t-1)&s)
      if(t&1<<low[s])res-=dfs(t,i)*c[A[s^t]][k-i];
  return res;
}

int main()
{
  n=read();m=read();
  for(int i=1,u,v;i<=m;i++){
    u=read()-1;v=read()-1;
    for(int s=0;s<(1<<n);s++)
      if((s&(1<<u|1<<v))==(1<<u|1<<v))A[s]++;
  }
  for(int s=0;s<(1<<n);s++)
    cnt[s]=cnt[s>>1]+(s&1),low[s]=(s&1)?0:low[s>>1]+1;
  for(int s=0;s<(1<<n);s++)
    for(int i=0;i<=m;i++)dp[s][i]=-1;
  for(int i=0;i<=m;i++)
    for(int j=c[i][0]=1;j<=i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];
  for(int i=1;i<=m+1;i++)ans+=1.0-dfs((1<<n)-1,i-1)/c[m][i-1];
  printf("%.6lf
",ans/(m+1));
  return 0;
}