UVa 10253 - Series-Parallel Networks

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給定 N 條邊,去除掉同構的情況,請問有多少個不同的串并連網路。

Sample Input

1
2
3
4
1
4
15
0

Sample Output

1
2
3
1
10
1399068

Solution

首先,拆分結果可以依序按照串-并-串-并 … 或者并-串-并-串 …

這樣會形成樹圖,其中奇數層是串/并,而偶數層是并/串,如此一來,要找到 N 個葉節點的樹有多少不同種的。根據兩種不同的分層方式,隨後乘上 2 就是答案。

定義 dp[i][j] 表示總共有 j 個葉節點的樹,並且每個子樹的葉節點最多 i 個 (至少)。這麼定義有它的好處,而不去直接定義 恰好

接著組合其具有 k 個樹-其子樹最多 i 個葉節點,剩下不足的葉節點,弄成一個樹,使用重複排列防止重複的計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h> 
#include <algorithm>
using namespace std;

long long dp[32][32] = {};
/*
parallel/series
consider parallel/series operation -> node,
n-edge == counting number of tree with n-leaf node.

dp[i][j]: at most i-leaves in subtree, total j-leaves.
dp[i][j] = \sum C(ret[i] + k - 1, k) \times dp[i-1][j - i*k]
^^^^^^^^^^^^^^^^^^^^[1] ^^^^^^^^^^^^^^^[2]
[1]: pick k subtree with at most (i-1)-leaves, total i-leaves
[2]: a subtree with at most (i-1)-leaves, total (j-i*k)-leaves
*/

long long C(long long n, long long m) {
long long ret = 1;
m = min(m, n-m);
for (long long i = 1; i <= m; i++)
ret = ret * (n + 1 - i) / i;
return ret;
}
int main() {

long long ret[32] = {};
ret[1] = 1;
for (int i = 1; i <= 30; i++)
dp[0][i] = 0, dp[i][1] = 1;
for (int i = 0; i <= 30; i++)
dp[i][0] = 1;
for (int i = 1; i <= 30; i++) {
for (int j = 2; j <= 30; j++) {
for (int k = 0; i * k <= j; k++) {
dp[i][j] += C(ret[i] + k - 1, k) * dp[i-1][j - i*k];
}
}
ret[i+1] = dp[i][i+1];
}

int n;
while (scanf("%d", &n) == 1 && n)
printf("%lld\n", n == 1 ? 1 : ret[n] * 2);
return 0;
}