题目大意:
1:一条单独的边是串并联网络
2:G1,G2为串并联网络, 将它们的源点与汇点分别连接起来, 得到的也是串并联网络(并联)
3:G1,G2为串并联网络, 将G1的汇点与G2的源点连接起来,得到的也是串并联网络(串联)
串联在一起的部分可以随意交换, 并联在一起的也可以随意交换顺序
要求:给n个点, 统计有多少种串并联网络。
思路:将这个网络简化成一颗树, 每颗子树就相当于一个网络, 那么有两种情况
1、根节点为并联网络
2、根节点为串联网络
由于顺序不影响结果, 所以这两种情况的结果是相等的,即只需要算出一种, 再乘以2即可得到答案
n个点, 即这颗树有n个叶子节点。
特例: n = 1的时候 只有一种结果
n >= 2时:
设f[i] 为叶子节点数为i的树的方案数, 则答案为:f[n](n > 1)
方法一:将n 进行整数拆分, 再对分拆数进行计算求和
方法二:设dp[i][j]为 每颗子树最大叶子节点数不超过i, 总叶子节点数为j 的方案数
则f[i] = dp[i-1][i]
而dp[i][j] = C(f[i] + p - 1, p) * dp[i - 1][j - p * i] (p * i <= j)
代码:
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 using namespace std;
6 #define MAXN 31
7 #define LL long long
8 LL f[MAXN];
9 LL dp[MAXN][MAXN];//dp[i][j] = C(f[i] + p - 1, p) * dp[i - 1][j - p * i];
10 int n;
11
12 LL C(LL n, LL k)
13 {
14 double ans = 1;
15 for(int i = 0; i < k; i ++)
16 ans = ans * (n - i);
17 for(int i = 1 ; i <= k; i ++)
18 ans = ans / i;
19 return (LL) (ans + 0.5);
20 }
21 void init()
22 {
23 for(int i = 0; i < MAXN; i ++) dp[i][0] = 1;
24 for(int i = 1; i < MAXN; i ++) dp[0][i] = dp[i][1] = 0;
25 f[1] = 1;
26 for(int i = 1; i < MAXN; i ++)
27 {
28 for(int j = 0; j < MAXN; j ++)
29 {
30 dp[i][j] = 0;
31 for(int p = 0; p * i <= j; p ++)
32 dp[i][j] += (C(f[i] + p - 1, p) * dp[i-1][j-p*i]);
33 }
34 f[i + 1] = dp[i][i + 1];
35 }
36 }
37
38 int main()
39 {
40 init();
41 while(scanf("%d",&n) && n)
42 {
43 printf("%lld\n", n == 1? 1 : 2 * f[n]);
44 }
45 return 0;
46 }