POJ 1737-Connected Graph【计数DP】

谁践踏了优雅 2023-08-17 15:46 8阅读 0赞

求 N 个节点的无向连通图有多少个，节点有标号，编号为1~N。

例如下列图示，三个节点的无向连通图共4个。

![1737\_1.jpg][1737_1.jpg]

输入格式

输入包含多组测试数据。

每组数据包含一个整数N。

当输入为0时，表示输入终止。

输出格式

每组测试数据输出一个结果，每个结果占一行。

数据范围

1≤N≤50

思路：这题要用高精度，我用py写的，可以在这里交[AcWing 307：连通图][AcWing 307]

首先对于n个点，可能会有的边是n\*(n - )/2, 那么n个点的所有无向图的数目是2 ^ n\*(n - )/2 , 连通图数 = 总数- k个联通块数（k>1）, 我们设f\[i\] 是i个节点的无向连通图个数，然后我们标号为i的节点所在的联通块中节点个数k，从n-1个节点中选择k-1个

，剩余的n-k个节点任意构成图，有2  ^ ((n - k) \* (n - k - 1) / 2) 方案。所以转移方程是：

f[i] = f[i] - f[j] * c(i - 1, j - 1) * 2 ** ((i - j) * (i - j - 1) // 2)

def c(n, m):
    
        n = int(n)
        m = int(m)
        ret = 1
        for i in range(n - m + 1, n + 1):
            ret = ret * i
        for i in range(1, m + 1):
            ret = ret // i
        return ret
    
    f = [0 for i in range(100)]
    x = 1
    
    f[1] = 1
    for i in range(2, 60):
        f[i] = 2 ** (i * (i - 1) // 2)
        for j in range(1, i):
            f[i] = f[i] - f[j] * c(i - 1, j - 1) * 2 ** ((i - j) * (i - j - 1) // 2)
    
    
    while 1:
        n = int(input())
        if n == 0:
            break
        print(f[n])

[1737_1.jpg]: /images/20230810/81151e3253634682a5bec59a000e99f5.png
[AcWing 307]: https://www.acwing.com/problem/content/309/

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关【计数DP】P4933 大师

这道是洛谷官方题单的简单DP 为啥我放上来呢，因为我因为各种各样的细节原因没做出来感觉计数的DP有点点难，得多写了 [P4933 大师 - 洛谷 | 计算机科学教育新生

╰+攻爆jí腚メ/ 2024年03月29日 16:21/ 0 赞/ 76 阅读

相关【计数DP】子序列个数

什么吊DP，根本不会 [题目-子序列个数 (51nod.com)][-_ _51nod.com] 题意： ![b111353c55234f59a30d1366d55a32

不念不忘少年蓝@/ 2024年03月22日 14:46/ 0 赞/ 81 阅读

相关【计数DP】CF1794D

[Problem - D - Codeforces][] 题意 ![06493c1d861a49e6995818c716958851.png][] 思路解法大方向对了

痛定思痛。/ 2024年02月21日 12:04/ 0 赞/ 67 阅读

相关 POJ 1737-Connected Graph【计数DP】

求 N 个节点的无向连通图有多少个，节点有标号，编号为1~N。例如下列图示，三个节点的无向连通图共4个。 ![1737\_1.jpg][1737_1.jpg] 输入格式

谁践踏了优雅/ 2023年08月17日 15:46/ 0 赞/ 9 阅读

相关 POJ1163DP

题意和解析，看代码最后部分 include <iostream> include <cstdio> include <cmath> using

淡淡的烟草味﹌/ 2022年08月18日 00:40/ 0 赞/ 31 阅读

相关计数（dp

描述：计算从1到n中，每个数字（0到9）出现的次数其中sum[j]和dp[i]表示：数字i中 j 的个数；比如sum[1]和dp[5]就可以表示：5中1的

梦里梦外;/ 2022年06月18日 00:29/ 0 赞/ 217 阅读

相关 Connected Graph

[Connected Graph][] 求n个点的无向联通图数量，\\(n\\leq 50\\)。解直接无向联通图做状态等于是以边点做考虑，难以去重，考虑联通对立

我不是女神ヾ/ 2022年01月08日 00:29/ 0 赞/ 234 阅读

相关【dp】POJ-1050

从里面任意截取一个矩阵,使得矩阵所包含的数字的和最大. 首先考察该题的简化版：已知一列数，求任意连续若干个数和的最大值。因为是连续若干个自然数的和，那前面的某个数字取

淩亂°似流年/ 2021年12月05日 13:09/ 0 赞/ 261 阅读

相关 poj1037（计数dp）

题意：给定n个数字，规定一种 cute 排序：序列中的数字大小为严格的波浪形，即 a\[0\] > a\[1\] < a\[2\] > a\[3\] < .... 或者 a\

àì夳堔傛蜴生んèń/ 2021年11月29日 14:42/ 0 赞/ 343 阅读

相关 POJ - 1737 Connected Graph（计数dp）

题意：求n个点组成的连通图的种数。分析：经典DP。详见《算法竞赛进阶指南》P337。代码： include <cstdio> includ

一时失言乱红尘/ 2021年11月29日 05:26/ 0 赞/ 245 阅读