【poj1737】 Connected Graph
2024-08-26 14:09:11
http://poj.org/problem?id=1737 (题目链接)
题意
求n个节点的无向连通图的方案数,不取模w(゚Д゚)w
Solution
刚开始想了个第二类斯特林数,然而并不知道怎么求具体方案,于是翻了题解。。
设${f_n}$表示n个节点的方案数。
那么n个节点所能够构成的无向图,无论连不连通,一共有${\frac{n*(n+1)}{2}}$条边,于是就有${2^{\frac{n*(n+1)}{2}}}$种图。考虑如何减去不连通的图的方案数。
我们选择枚举1号节点与i个节点连通,则${1<=i<=n-2}$(因为要保证不连通)。
那么这i个点的选择方案有${C^{i}_{n-1}}$种
整个1号节点的联通块有${f_{i+1}}$种连接方式
连通块以外的节点又有${2^{\frac{(n-i-1)*(n-i)}{2}}}$种连接方式
所以得到递推式就是:
$${f_n=2^{\frac{n*(n+1)}{2}}-\sum^{n-2}_{i=1}{C^{i}_{n-1}×f_{i+1}×2^{\frac{(n-i-1)*(n-i)}{2}}}}$$
细节
我已经预见到了自己10kb的程序。。于是随便蒯了个Java切了。。
代码
坑着
最新文章
- LeetCode Fizz Buzz
- fail to create java virtual machine..
- 使用View为Data Source的Form开发要点
- 配置超级用户口令(Cisco IOS系统)
- CoreText中坐标转换的一些理解
- That&#39;s life,多一些韧性,才有更多的任性(转)
- 判断activity是否显示在界面上
- A - 棋盘问题 POJ - 1321
- JaveScript简单数据类型(JS知识点归纳二)
- ssh框架-Struts2(二)
- 18. 4Sum(中等)
- PHP中的表单传值
- 【C++】C++中的基本内置类型
- [UE4]Spin Box,数字输入,可拖动
- B. Math
- C++ one more time
- 为什么要用lock 【readonly】object?为什么不要lock(this)?
- [微信小程序] 微信小程序获取用户定位信息并加载对应城市信息,wx.getLocation,腾讯地图小程序api,微信小程序经纬度逆解析地理信息
- 【Python】Python中的深浅拷贝
- unity3d NGUI 本地化 多语言