首页 > 专题系列 > Java解POJ > POJ 1737 Connected Graph [解题报告] Java
2013
11-10

POJ 1737 Connected Graph [解题报告] Java

Connected Graph

问题描述 :

An undirected graph is a set V of vertices and a set of E∈{V*V} edges.An undirected graph is connected if and only if for every pair (u,v) of vertices,u is reachable from v.

You are to write a program that tries to calculate the number of different connected undirected graph with n vertices.

For example,there are 4 different connected undirected graphs with 3 vertices.

输入:

The input contains several test cases. Each test case contains an integer n, denoting the number of vertices. You may assume that 1<=n<=50. The last test case is followed by one zero.

输出:

For each test case output the answer on a single line.

样例输入:

1
2
3
4
0

样例输出:

1
1
4
38

解题代码:

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

public class Main
{
   BigInteger[] ans = new BigInteger[52];
   public Main()
   {
      DP();
      solve();
   }
   //姹�����
   BigInteger combinationNum(int n, int m)
   {
      BigInteger ret = new BigInteger("1");
      int i;
      for (i = 0; i < m; ++i)
      {
         ret = ret.multiply(new BigInteger(n - i + ""));
         ret = ret.divide(new BigInteger(i + 1 + ""));
      }
      return ret;
   }

    void DP()
   {
      ans[1] = new BigInteger("1");
      ans[2] = new BigInteger("1");
      int i, j;
      BigInteger tmp = new BigInteger("0");
      BigInteger com = new BigInteger("0");
      for (i = 3; i <= 50; ++i)
      {
         ans[i] = new BigInteger("0");
         for (j = 1; j < i; ++j)
         {
            com = combinationNum(i - 2, j - 1);
            tmp = ans[j].multiply(ans[i - j]);
            tmp = tmp.multiply(com);
            tmp = tmp.multiply(new BigInteger(((long)1 << j) - 1 + ""));
            ans[i] = ans[i].add(tmp);
         }
      }
      //for (i = 1; i <= 50; ++i)
      //   System.out.println(i + ": " + ans[i]);
   }
    void solve()
    {
       int n;
       Scanner cin = new Scanner(System.in);
       while (true)
       {
          n = cin.nextInt();
          if (n == 0)
             return;
          System.out.println(ans[n]);
       }
    }

   public static void main(String args[])
   {
      new Main();
   }
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。