搬运自洛谷文章：边数确定的无向图的简单路径条数最大值。
起因是洛谷省选计划答疑有人问了，然后我不会做，也没搜到，后来问了下 Tony2 老师得到了答复，感觉很聪明于是记录一下。
问题是，给定 $m$，求有 $m$ 条边的无向图的简单路径条数最大值，但是这东西显然确切解很困难，即使是求大概的复杂度也比较难，所以求一个它的对数的界。
有构造，将一堆四元环 $a, b, c, d$ 连起来，就是 $a$ 连前面的 $d$ 连后面的环，显然路径数大概是 $m^2 2 ^ {m/4}$ 左右的，取对数是 $\Theta(m)$。
有上界是（假设连通）所有点的度数加一的乘积，因为每个点只能走一次，所以考虑选择一个后继的边，不用考虑是否组成路径。度数加一之和是 $O(m)$ 的，而把一个数 $x$ 拆成一些数的乘积使其最大，这是经典问题，答案是 $3^{x/3}$ 左右的，于是原问题对数的上界就是 $O(m)$。复杂度上界是 $O(3 ^ {m})$。
于是就得到了原问题对数的一个复杂度的界。
但是还不知道更进一步怎么做！原问题能不能确定最优解的复杂度呢！更进一步，能不能确定最优解的具体解析解呢！大家教教。以及有相关文章也欢迎评论！
有一个优化的构造方式是，如果能找到一张图，使得花费了 $a$ 条边，从某个出发点到某个终止点有 $b$ 条路径，那就有一个 $\Theta(b ^ {\frac{m}{a}})$ 的构造方法。
2025-2-23 13:45 UPD：adjective 老师提出了，如果确定起点为某个点的话，令 $f _ m$ 表示简单路径数，那么有 $f_i \le \max_{d=1}^{i} df_{i-d} + 1$，$f_0 = 1$。也就是，把 $m$ 拆成一列数字 $a _ 1, \ldots, a _ k$，然后是它的所有后缀的乘积之和。最优解里数列一定是单调不降的，而且开头不会有太多的 $1$（有多个的话合并起来答案不变），所以这个最大值和所有数乘积最大值同阶，就是 $O(3 ^ {\frac{m}{3}})$，再乘上开始的点的选法就是 $O(m3 ^ {\frac{m}{3}})$，于是上界变小了！
2025-3-3 14:55 UPD：如果允许重边，就可以造一个 $\frac m 3$ 个点的环，这样就是 $O(m3^{\frac{m}{3}})$ 的路径数了，达到了上界（）
