没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
Connected Graph
求 N 个顶点的连通图的个数。 N<=50, 每
个顶点看成是不同的。
方法是显然要 Dp 了。
方法一
方法一
S[x, y] 表示一个已连通的 x 个点的团和 y
个孤立点组成连通图的方案数。
F[N] = S[1, N - 1];
对 S[x, y] 用记忆化搜索。转移时枚举有几
个 y 直接连向 x 。
只是跑的太慢最多只能打表交了 ....
O(N^3* 高精 )
方法二
方法二
记 F[N] 就是答案 ,G[N] 是 2^(N*(N-1)/2)-F
[N];
我们这么计算 G[N] 。枚举和第一个点连通
的有多少个点 , 余下的点任意。
所以 Sum{C(i-1,N-1)*F[i]*2^((N-j)*(N-j-1)/
2),i=1…N-1}
O(N^2* 高精 )
剩余24页未读,继续阅读
资源评论
skyguller
- 粉丝: 3
- 资源: 157
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功