Uva_10253 Series-Parallel Networks
Uva_10253 Series-Parallel Networks
若羽
发布于 2019-07-15 16:33:38
发布于 2019-07-15 16:33:38
题目大意：
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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-07-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读