题意比较简单，就是求N个节点，任意连无向边，两点间只能连一条无向边，问说连通的无向图的个数，和USETC的2010第一场集训队选拔赛题目类似，就是要求补集的个数，然后用总个数减去就行。设E=C(N,2),则无向图的总个数是2^E个。然后就是求不连通的无向图的个数。固定其中一个点O，选择K个点，点O在这K个点中，对剩下的N-K个点随便连，而这K个点求连通，这里的固定一个点很巧妙，避免的重复的情况。通过这道题同时练习了Java的大整数的一些操作，乘法，减法，加法，次幂。
代码 1 import java.io. * ; 2 import java.math. * ; 3 import java.util. * ; 4 5 public class Main 6 { 7 static BigInteger two = BigInteger.valueOf( 2 ); 8 static BigInteger dp[] = new BigInteger[ 55 ]; 9 static BigInteger c[][] = new BigInteger[ 55 ][ 55 ]; 10 public static void ready() 11 { 12 for ( int i = 0 ; i <= 50 ; i ++ ) for ( int j = 0 ; j <= i; j ++ ) 13 { 14 if (j == 0 || i == j) c[i][j] = BigInteger.ONE; 15 else c[i][j] = c[i - 1 ][j].add(c[i - 1 ][j - 1 ]); 16 } 17 for ( int i = 0 ; i <= 50 ; i ++ ) dp[i] = BigInteger.ZERO; 18 } 19 public static BigInteger go( int n) 20 { 21 if (n == 1 ) return BigInteger.ONE; 22 if (dp[n] != BigInteger.ZERO) return dp[n]; 23 BigInteger res = two.pow(n * (n - 1 ) / 2 ); 24 for ( int k = 1 ; k < n; k ++ ) 25 { 26 BigInteger t = c[n - 1 ][k - 1 ]; 27 t = t.multiply(go(k)); 28 t = t.multiply(two.pow((n - k) * (n - k - 1 ) / 2 )); 29 res = res.subtract(t); 30 } 31 dp[n] = res; 32 return res; 33 } 34 public static void main(String[] args) { 35 ready(); 36 Scanner cin = new Scanner(System.in); 37 while (cin.hasNext()) 38 { 39 int n = cin.nextInt(); 40 if (n == 0 ) break ; 41 System.out.println(go(n)); 42 } 43 } 44 }
转载于:https://www.cnblogs.com/litstrong/archive/2010/05/25/1743867.html
相关资源：数据结构—成绩单生成器