「UVa 10253」Series-Parallel Networks - 整数划分 + 组合数

串并联网络有两个端点,一个是源,一个是汇,递归定义如下:

  1. 一条单独的边是串并联网络;
  2. G1 G2 是串并联网络,则将它们的源和汇分别接在一起也能得到串并联网络(并联);
  3. G1 G2 是串并联网络,则将 G1 的源和 G2 的汇接在一起也能得到串并联网络(串联);

并联或串联在一起的各个部分可以调换顺序,顺序改变后的串并联网络和之前是相同的。求 N 条边能组成多少种不同的串并联网络。

链接

UVa 10253

题解

书上的解法,考虑每个串并联网络都是一棵树,组成网络的几个部分是树的子节点,那么叶子节点就对应了网络中的边,并且整棵树从根到叶子,父子关系所代表的连接方式是交替着的,某一层是并联,则下一层即为串联。同一种树的形态,第一层的连接方式不同,也就对应了两个网络。

问题转化为,求有多少子节点有序且有 N 个叶子节点的形态不同的树。设 f(n) 为答案,则可以根据各个子树所『分得』的叶子节点数量来递归求解 —— 回溯法枚举 n 整数划分,就得到了单层子树所有的情况。

假设整数划分的某一种方案中,有 k i ,求这 k 棵子树的方案数可使用组合数:从 f(i) 个中选择 k 个,可重复选择,答案为 \binom{f(i) + k - 1}{k} 。计算出每一组子树的方案数,相乘即为根节点的答案。

最终答案为 f(n) * 2 ,注意 n = 1 时答案为 1

代码

#include <cstdio>
#include <vector>

const int MAXN = 30;

long long solve(int n);
void search(std::vector<int> &v, int t, int r);

long long C(long long n, long long m) {
    long long result = 1;
    for (int k = 1; k <= m; k++) {
        result = result * (n - k + 1) / k;
    }
    return result;
}

long long process(std::vector<int> &v) {
    long long ans = 1;
    int count = 0, last = 0;
    for (int i = 0; i < (int)v.size(); i++) {
        if (last != v[i] && last != 0) {
            ans *= C(solve(last) + count - 1, count);
            count = 1;
        } else {
            count++;
        }

        last = v[i];
    }

    ans *= C(solve(last) + count - 1, count);

    // printf("process = %lld\n", ans);
    return ans;
}

long long divide(std::vector<int> &v, int r, int t = 1) {
    if (r == 0) {
        if (v.size() == 1) return 0;
        // for (std::vector<int>::const_iterator p = v.begin(); p != v.end(); p++) printf("%d ", *p);
        // putchar('\n');
        // return 0;
        return process(v);
    }

    long long ans = 0;
    for (int i = t; i <= r; i++) {
        v.push_back(i);
        ans += divide(v, r - i, i);
        v.pop_back();
    }

    return ans;
}

long long solve(int n) {
    static long long mem[MAXN];
    static bool calced[MAXN];
    long long &ans = mem[n - 1];

    if (calced[n - 1]) return ans;
    calced[n - 1] = true;

    if (n == 1) return ans = 1;

    std::vector<int> v;
    ans = divide(v, n);

    // printf("f(%d) = %lld\n", n, ans);
    return ans;
}

int main() {
    for (int n; ~scanf("%d", &n) && n != 0; printf("%lld\n", n == 1 ? 1 : solve(n) * 2));
    return 0;
}