$Poj1737\ Connected\ Graph$ 计数类$DP$
2024-10-08 05:09:58
Description
求$N$个节点的无向连通图有多少个,节点有标号,编号为$1~N$.
$1<=N<=50$
Sol
在计数类$DP$中,通常要把一个问题划分成若干个子问题,以便于执行递推.
一个连通图不容易划分,而一个不连通的无向图则很容易划分成结点更少的两部分.所以我们把问题转化成用$N$个点的无向图总个数减去$N$个点的不连通无向图的个数.
$N$个点的无向图总个数显然是$2^{N*(N-1)/2}$,还是简单说下叭,就是$N$个点连成完全图的边数显然是$N*(N-1)/2$,然后每条边都可取可不取,所以就是$2^{N*(N-1)/2}$.
现在我们要把问题划分成互斥的子问题 $OvO$.不连通的图由若干个连通图构成.我们可以枚举$1$结点所在的联通块包含的结点数$k$,从$2~N$这$N-1$个结点中选出$k-1$个结点,显然有$C_{N-1}^{k-1}$种.剩余$N-k$个结点构成任意无向图,显然有$2^{(N-k)*(N-k-1)/2}$种.
$F[i]$表示$i$个结点构成的无向连通图个数.
$F[i]=2^{i*(i-1)/2}-\sum_{j=1}^{i-1}F[j]*C_{i-1}^{j-1}*2^{(i-j)*(i-j-1)/2}$
$F[1]=1$,答案为$F[N]$
Code
本来我已经信心满满地开始写了,突然发现还要高精 : )).我咕咕咕了.也许明天会写???
最新文章
- MVVM页面跳转 技巧性标记
- css学习归纳总结(一) 转
- thinkphp笔记
- PostgreSQL Replication之第十章 配置Slony(2)
- HDU 1010 Tempter of the Bone --- DFS
- Form实现无刷新上传文件并返回自定义值
- J2SE知识点摘记(二)
- WEB相关协议
- Java命令参数说明
- 如果Centos没有桌面,怎么修改IP地址
- candy(动态规划)
- 一个使用 Python 的人工智能聊天机器人框架
- SpringCloud-Greenwich版本新特性探索(1)---SpringCloudGateway
- SQL Server-聚焦事务、隔离级别详解(二十九)
- 网络编程,socket
- 兼容ie,火狐的判断回车键js脚本
- Jmeter—实现识别验证码登录
- mysql 限制sql执行时间
- HTML入门(三)后台系统显示页面_框架标签
- Friendly Date Ranges
热门文章
- HZOJ 光
- Android Studio(六):Android Studio添加注释模板
- hdu 3982 Harry Potter and J.K.Rowling (半平面交 + 圆与多边形交)
- 在对文件进行随机读写,RandomAccessFile类,如何提高其效率
- uva 624 CD (01背包)
- Mule自带例子之stockquote
- python的if判断
- C# 序列类为 xml 可以使用的特性大全
- Scheduler
- win10 uwp win2d CanvasVirtualControl 与 CanvasAnimatedControl