解題區/解題區 - UVa

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;
}