当前位置: 首页 > news >正文

解题报告-拯救计划(概率 DP)

拯救计划

题目背景

有一天,地球护卫队的 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)\) 的改变:

  1. 如果这次连边没有改变状态,那么有 \(g(S)=p \times ( g(S)+1 )\)
  2. 如果这次连边改变了状态,那么有 \(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;
}
http://www.hskmm.com/?act=detail&tid=37634

相关文章:

  • 日志分析-IIS日志分析
  • Min_25 筛
  • 解码Linux文件IO之库的制作与应用
  • 20251023 正睿二十连测
  • 1019:浮点数向零舍入(分正负取整)
  • 二分图/忆re.
  • 《IDEA 2025长效采用配置指南:有效期配置至2099年实战之JetBrains全家桶有效》​
  • ZKW线段树
  •  pytorch 66页实验题
  • Visual Studio 插件 - 喝水提醒 - 指南
  • JAVA 排序用法
  • 10/23
  • 10月23日
  • 第3天(中等题+简单题 数组、滑动窗口)
  • esp32-usb-jtag 调试踩坑
  • MySQLDay3
  • 飞牛OS通过docker部署SillyTavern酒馆
  • MySQL主从同步读写分离
  • ollama v0.12.2 版本更新详解:Qwen3 架构协助、Multi-Regex 分词器、新引擎前后缀匹配等功能升级
  • AI股票预测分析报告 - 2025年10月23日 20:26
  • 软件包管理
  • nginx反向代理测试搭建
  • 基础概念
  • .NET Core报错克服【无废话上操作】
  • 题解:P11831 [省选联考 2025] 追忆
  • 2025-10-23 MX-S 模拟赛 赛后总结【MX】
  • PCL1.12 解决memory.h中EIGEN处中断问题
  • 完整教程:状态管理库 Zustand 的接入流程与注意点
  • 20251023
  • Java常用机制 - SPI机制详解