题解：P3343 [ZJOI2015] 地震后的幻想乡

_Kenma_ · 2026-06-08 17:34:15 · 题解

简单题，速溶了。

首先发现题面里存在一个大大的提示，那么我们就从提示入手来做。容易发现我们只关心最后添加的一条边在 m 条边中的排名。

设 p_i 表示添加 i 条边后图恰好联通的概率，那么答案可以写成：

然后这个形式可以拆，另设 P_i 表示添加了 i 条边后图依然不连通的概率，那么答案可以写成：

现在我们要求 P_i，带着概率做是不好做的，求方案数除以总方案数 \dbinom{m}{i} 即可。

然后现在就变成了计数问题。也就是我们要算添加 i 条边图依然不连通的方案数。状压 DP，设 f_{s,i,0/1} 表示考虑 s 集合内的点，添加 i 条边后图是否连通的方案数，转移考虑容斥，点一个和集合内最小点连通的连通块即可，也就是：

其中 h_s 表示 s 的导出子图的边数。

复杂度 O(3^nm^2)，可以通过。

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define lowbit(i) (i&(-i))
int n,m,x[1025],y[1025],C[1025][1025],h[1025],f[1025][1025][2];
double ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    C[0][0]=1;
    for(int i=1;i<=m;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    for(int i=1;i<=m;i++) cin>>x[i]>>y[i],x[i]--,y[i]--;
    for(int s=0;s<(1<<n);s++) for(int i=1;i<=m;i++) if(s&(1<<x[i]) && s&(1<<y[i])) h[s]++;
    for(int s=1;s<(1<<n);s++){
        for(int t=s;t;t=(t-1)&s) if(lowbit(s)==lowbit(t)) for(int i=0;i<=h[t];i++) for(int j=0;j<=h[s^t];j++) f[s][i+j][0]+=f[t][i][1]*C[h[s^t]][j];
        for(int i=0;i<=h[s];i++) f[s][i][1]=C[h[s]][i]-f[s][i][0];
    }
    for(int i=0;i<=m;i++) ans+=1.0*f[(1<<n)-1][i][1]/C[m][i];
    ans/=(m+1);
    ans=1-ans;
    printf("%.6lf",ans);
    return 0;
}