poj 1737

本题是一道DP较为经典的题目，将规模分解变小。
题意非常简单，求n个点的连通图个数。（n<=50）
由于数据量较大，必须使用高精度，代码会显得非常长。这里使用java秒过。
思路：使用n个点构成图全部方案数减去不连通图的个数。
设F[n]表示n个点的不连通图的个数
设a[n]表示n个点的连通图的个数
则F[n]=sum{ c(n-1,k-1) * 2^(c(n-k,2)) * a[k] }  1<=k<=n
//除去第n个点，我们需要从剩余的n-1个点中选取k-1个点，作为第n个点所在的连通分支并且连通分支的总点数位k，剩余的n-k个点任意构图，最后再乘以k个点可以构成的连通图的个数即可。

所以a[n]= 2^(c(n,2))-F[n]

java代码如下：

 

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    static public BigInteger cal(int n, int k) {
        BigInteger ret = new BigInteger("1");
        for (int i = n; i > n - k; i--)
            ret = ret.multiply(BigInteger.valueOf(i));
        for (int i = 1; i <= k; i++)
            ret = ret.divide(BigInteger.valueOf(i));
        return ret;
    }

    static public void main(String[] args) {
        BigInteger a[] = new BigInteger[51];
        a[1] = new BigInteger("1");
        for (int i = 2; i <= 50; i++) {
            a[i] = new BigInteger("0");
            for (int j = 1; j < i; j++) {
                a[i] = a[i].add(a[j].multiply(cal(i - 1, j - 1).multiply(new BigInteger("2").pow((i - j) * (i - j - 1) / 2))));
            }
            a[i] = new BigInteger("2").pow(i * (i - 1) / 2).subtract(a[i]);
        }
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        while (cin.hasNext())
        {
            int x = cin.nextInt();
            if (x == 0)
                return;
            System.out.println(a[x]);
        }
    }
}