10253 Series-Parallel Networks
In this problem you are expected to count two-terminal series-parallel networks. These are electric
networks considered topologically or geometrically, that is, without the electrical properties of the
elements connected. One of the two terminals can be considered as the source and the other as the
sink.A two-terminal network will be considered series-parallel if it can be obtained iteratively in the
following way:
• A single edge is two-terminal series-parallel.
• If G1 and G2 are two-terminal series-parallel, so is the network obtained by identifying the sources
and sinks, respectively (parallel composition).
• If G1 and G2 are two-terminal series-parallel, so is the network obtained by identifying the sink
of G1 with the source of G2 (series composition).
Note here that in a series-parallel network two nodes can be connected by multiple edges. Moreover,
networks are regarded as equivalent, not only topologically, but also when interchange of elements in
series brings them into congruence; otherwise stated, series interchange is an equivalence operation. For
example, the following three networks are equivalent:
Similarly, parallel interchange is also an equivalence operation. For example, the following three
networks are also equivalent:
Now, given a number N, you are expected to count the number of two-terminal series parallel
networks containing exactly N edges. For example, for N = 4, there are exactly 10 series-parallel
networks as shown below:
Input
Each line of the input file contains an integer N (1  N  30) specifying the number of edges in the
network.
A line containing a zero for N terminates the input and this input need not be considered.
Universidad de Valladolid OJ: 10253 – Series-Parallel Networks 2/2
Output
For each N in the input file print a line containing the number of two-terminal series-parallel networks
that can be obtained using exactly N edges.
Sample Input
14
15
0
Sample Output
1
10
1399068

题意：

       串并联网络有两个端点，一个叫源，一个叫汇，递归定义如下：

（1）       一条单独的边是串并联网络。

（2）       若G1和G2是串并联网络，把它们的源和源接在一起、汇接在一起也能得到串并联网络。

（3）       若G1和G2是串并联网络，把G1的汇和G2的源接在一起也能得到串并联网络。

其中规则（2）指的是并联、规则（3）指的是串联。串并联网络中两点之间可以有多条边，串联或者并联在一起的各个部分可以任意调换顺序。

输入正整数n(1<=n<=30)，统计有多少个n条边的串并联网络。

分析：

       将每个串并联网络看成一棵树。为每次串联或者并联创建一个结点（串联、并联结点），并且将所有串联或并联的部分看成该结点的子树。假设根结点是并联结点，那么第二层的非叶结点一定是串联结点，第三层的非叶结点一定是并联结点…….这样就可以知道所有非叶结点的类型，于是我们并不需要关心非叶结点的类型，只需要计算f(n)=“共n个叶子，每个非叶结点至少有两个子结点的树的个数”，答案就为2*f(n)。

       设状态d(i,j)表示每棵子树最多包含i个叶子、一共有j个叶子的树的个数。于是f(n)=d(n-1,n)。假设恰好包含i个叶子的子树有p棵，那么这些树的组合数等于从f(i)棵树中选择p棵树的方案数，即C(f(i)+p-1,p)，因此d(i,j)=sum{C(f(i)+p-1,p)*d(i-1,j-p*i) | p>=0,p*i<=j}

边界是：i>=0时d(i,0) = 1,i>=1时d(i,1) = 1,但d(0,i) = 0。

 1 #include <cstdio> 2 #include <cstring> 3 long long C(long long n,long long m){ // 组合数 4     double ans = 1; 5     for(int i = 0 ; i < m ; i++) ans *= (n - i); 6     for(int i = 0 ; i < m ; i++) ans /= (i + 1); 7     return (long long)(ans + 0.5); 8 } 9 const int maxn = 30;10 long long f[maxn + 1];11 long long d[maxn + 1][maxn + 1];12 int main(){13     f[1] = 1;14     memset(d,0,sizeof d);15     int n = 30;16     for(int i = 0 ; i <= n ; i++) d[i][0] = 1;17     for(int i = 1 ; i <= n ; i++) d[i][1] = 1,d[0][i] = 0;18     for(int i = 1 ; i <= n ; i++){19         for(int j = 2 ; j <= n ; j++){20             d[i][j] = 0;21             for(int p = 0 ; p * i <= j ; p++)22                 d[i][j] += C(f[i] + p - 1,p) * d[i - 1][j - p * i];23         }24         f[i + 1] = d[i][i + 1];25     }26     while(scanf("%d",&n) == 1 && n)27         printf("%lld\n",n == 1 ? 1 : 2 * f[n]);28     return 0;29 }

View Code

UVa10253