📅 发布时间：2026/6/20 21:08:50

拯救计划

题目背景

有一天，地球护卫队的 P 队长得知，邪恶的 Y 星球要向地球发起侵略。正义感责任感极强的小 P 怎么可能允许这类事情发生。为了小 W，同时也为了保卫地球，小 P 准备动员所有力量殊死一战，正当小 P 带领部队准备迎敌的时候突然发现。很多城市之间的道路都坏了，仅剩下几条道路可以通过。小 P 毅然决定一定要赶紧修建一些道路使得所有的城市连通，可是负责修建道路的人实在是太懒了。每次总是随机的选取两个不同的点之间进行修建道路，于是小 P 想要知道期望修建多少条道路才可以使图连通。

题目描述

给定一个有 \(N\) 个点和 \(M\) 条边的无向图，可以进行若干次连边操作，每次操作添加一条边把随机两个不同点相连。

现在要使这个图完全连通（所有点处于一个连通块中），求出所需的连边操作次数的期望。

注意：边 \((u,v)\) 和 \((v,u)\) 是同一条边。

输入描述

第一行为 \(N\)、\(M\)，表示无向图的节点数和边数。

下面的 \(M\) 行，每行 \((X,Y)\) 表示连接 \(X\) 和 \(Y\) 的一条边。

输出描述

仅一行，为期望操作数，结果保留 \(6\) 位小数。

输入输出样例 #1

输入样例 #1

2 1
1 2

输出样例 #1

0.000000

输入输出样例 #2

输入样例 #2

4 2
1 2
3 4

输出样例 #2

1.500000

提示/说明

数据范围

对于 \(100\)% 的数据，\(N \leq 30\)，\(M \leq 1000\)，\(1 \leq X,Y \leq N\)。

解题报告

好样的题目，原地暴毙，数学残疾人是这样的。

其实中规中矩的推导就行了。

首先，点的编号肯定是无意义的，我们只关心图的连通块的状态，更进一步，我们只关心当前图中每个连通块的大小。

约定符号表示：

设当前无向图中有 \(k\) 个连通块，第 \(i\) 个连通块的大小为 \(siz_i\)。
设当前无向图的状态集合为 \(S=\{siz_1,siz_2,\cdots,siz_k\}\)，为了使状态集合与无向图一一对应，同时因为各个连通块地位上是等价的，不妨设 \(siz_1 \leq siz_2 \leq \cdots \leq siz_k\)。
设 \(S'\) 表示一次连边操作把连通块 \(i\) 和 \(j\) 相连后的新图的状态集合。
设 \(g(S)\) 表示使当前无向图完全连通所需的操作次数的期望值。
设 \(T\) 表示连边操作的情况总数，\(T=\dfrac{n(n-1)}{2}\)。
设 \(p\) 表示在当前图中，进行一次连边后不造成状态改变的概率，\(p=\dfrac{\sum_{i=1}^{k} \binom{siz_i}{2}}{T}\)。

根据上面的定义，有：\(p+\sum_{i=1}^{k}\sum_{j=1}^{i} \dfrac{siz_i \times siz_j}{T}=1\)，这是由于 \(\sum_{i=1}^{k} \binom{siz_i}{2}+\sum_{i=1}^{k}\sum_{j=1}^{i} (siz_i \times siz_j)=T\)，等式左边表示连边的情况总数。

下面推导一次连边后 \(g(S)\) 的改变：

如果这次连边没有改变状态，那么有 \(g(S)=p \times ( g(S)+1 )\)。
如果这次连边改变了状态，那么有 \(g(S)=\sum_{i=1}^{k}\sum_{j=1}^{i}(\dfrac{siz_i \times siz_j}{T}\times (g(S')+1))\)。

所以有：

\[g(S)=p \times ( g(S)+1 ) + \sum_{i=1}^{k}\sum_{j=1}^{i}(\dfrac{siz_i \times siz_j}{T}\times (g(S')+1)) \\ g(S)=p\times g(S)+p+\sum_{i=1}^{k}\sum_{j=1}^{i}(\dfrac{siz_i \times siz_j}{T}\times g(S'))+\sum_{i=1}^{k}\sum_{j=1}^{i}\dfrac{siz_i \times siz_j}{T} \\ (1-p)\times g(S)=(p+\sum_{i=1}^{k}\sum_{j=1}^{i}\dfrac{siz_i \times siz_j}{T})+\sum_{i=1}^{k}\sum_{j=1}^{i}(\dfrac{siz_i \times siz_j}{T}\times g(S')) \\ (1-p) \times g(S)=1+\sum_{i=1}^{k}\sum_{j=1}^{i}(\dfrac{siz_i \times siz_j}{T}\times g(S')) \\ g(S)=\dfrac{1+\sum_{i=1}^{k}\sum_{j=1}^{i}(\dfrac{siz_i \times siz_j}{T}\times g(S'))}{1-p} \]

可以用并查集维护原图的连通块，记忆化搜索处理 \(g(S)\)，直接用 C++ 的 \(\text{map}\) 容器存结果，反正数据范围这么小。

额外求一下时间复杂度，设 \(F(n,k)\) 表示把无向图的 \(n\) 个无序号点划分成最大部分不超过 \(k\) 方案数。

有递推式 \(F(n,k)=F(n-k,k)+F(n,k-1)\)。

那么时间复杂度为 \(O(F(n,n) \times n^2) \leq O(5604 \times 30^2)\)，代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=(1E+9)+7;
const int N=101;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}int n,m,all;// ---并查集---int dad[N],siz[N];inline void Clearset()
{for(int i=1;i<=n;i++)dad[i]=i,siz[i]=1;
}int findset(int x)
{if(dad[x]==x) return x;return dad[x]=findset(dad[x]);
}inline void mergeset(int u,int v)
{u=findset(u),v=findset(v);if(u==v) return ;dad[v]=u; siz[u]+=siz[v];
}// ---记忆化搜索---map<vector<int>,double > dp;
vector<int> st;double dfs(vector<int> u)
{if(dp.count(u)) return dp[u];if(u.size()==1) return dp[u]=0;int len=u.size();double p=0;for(int i=0;i<len;i++)p+=u[i]*(u[i]-1)/2;double tmp=0; p/=all;for(int i=1;i<len;i++)for(int j=0;j<i;j++){vector<int> v=u;v[i]+=v[j];swap(v[j],v[len-1]);v.pop_back();sort(v.begin(),v.end());tmp+=u[i]*u[j]*dfs(v)/(double)all;}tmp=(1.0+tmp)/(1-p);return dp[u]=tmp;
}signed main()
{freopen("interconnect.in","r",stdin);freopen("interconnect.out","w",stdout);n=read(),m=read(); Clearset();for(int i=1;i<=m;i++)mergeset(read(),read());all=(n-1)*n/2;for(int i=1;i<=n;i++)if(findset(i)==i)st.push_back(siz[i]);sort(st.begin(),st.end());dfs(st);printf("%.6lf",dp[st]);return 0;
}

解题报告-拯救计划（概率 DP）