PKU 1737解題報告Connected Graph_高精度加算、乗算、減算、組合せ数

Connected Graph
 リンクアドレス
http://acm.pku.edu.cn/JudgeOnline/problem?id=1737
 時空の制限
Time limit:1 Seconds   Memory limit:30000K
テーマの内容
Description
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.
 
 
 
 
Input
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.
Output
For each test case output the answer on a single line.
Sample Input

1

2

3

4

0

 
Sample Output
1
1
4
38
Source
LouTiancheng@POJ
 
 
解題構想(アルゴリズム)
テーマは大体n個の点を与えて、このn個の点の連通図の個数を求めることを意味します.
n個の点をg(n)で表すと、n*(n-1)/2個の辺があるのに対し、n*(n-1)/2個の辺がつながっているか、つながっていないかの2つの可能性があるため、g(n)=2^(n-(n-1)/2)
従って、連通図の個数=総図の個数−連通図の個数ではない.
それはf(n)にn個の点の連通図の個数を表す.
連通しない図の個数は、頂点数がn未満の連通図の個数に残りの頂点を乗じた合計図の個数、すなわち
;図:
                  
だから
でも...
本当にCinなのか、一例を見てみましょう
 
1)
    2)
 
 
 
1)と2)は実は同じ状態であるが,計算によって(1,2)が1種,選択(3,4)が1種であるため重複が生じる.
では、どのように修正すればいいのでしょうか.実は、1つの点を固定し、1と仮定し、n-1の点の中からi-1の点を選んで1と連通図であるCi-1 n-1を構成すれば、重複を避けることができます.
総合:
n=11でデータが
356775920067776576です.
N=12なら__を超えるint 64の範囲です.
だからこの問題は必ず高精度に使わなければならない.
f,Cinを計算するときにf,Cinを算出して保存し,計算を繰り返さないようにしないとタイムアウトする可能性がある.
もう一つ注意したいのは、Cinを計算する際に式Cin=Ci-1 n+Ci-1 n-1を用いることで、高精度加算で推定できることです.
プログラムコード
#include
#include
int CC[60][60][400];
int FF[60][1000];
int GG[60][1000];
int gjd_add(int *a,int *b,int *c)
{
  int i;
  for(i=*a+1;i<=*a+*b+5;i++) a[i]=0;
  for(i=*b+1;i<=*a+*b+5;i++) b[i]=0;
  for(i=1;i<=(*a+*b+5);i++) c[i]=a[i]+b[i];
  for(i=1;i<=*a+*b+3;i++)
      {
       c[i+1]=c[i+1]+c[i]/10;
       c[i]=c[i]%10;
      }
  for(i=*a+*b+4;i>=1;i--)
    if (c[i]) break;
  c[0]=i;
  return i;
}
int gjd_min(int *a,int *b)
{
  int i;
  for(i=1;i<=*b;i++)
     a[i]=a[i]-b[i];
  for(i=1;i<=*a;i++)
      if (a[i]<0)
      {
        a[i+1]--;
        a[i]+=10;
      }
  for(i=*a;i>=1;i--)
    if (a[i]) break;
  a[0]=i;
  return i;
}
int gjd_mul(int *a,int *b,int *c)
{
  int i,j;
  for(i=*a+1;i<=*a+*b+5;i++) a[i]=0;
  for(i=*b+1;i<=*a+*b+5;i++) b[i]=0;
  for(i=0;i<=*a+*b+5;i++) c[i]=0;
  for(i=1;i<=*a;i++)
   for(j=1;j<=*b;j++)
     c[i+j-1]+=a[i]*b[j];
   for(i=1;i<=*a+*b+5;i++)
   {
      c[i+1]=c[i+1]+c[i]/10;
       c[i]=c[i]%10;
   }
   for(i=*a+*b+5;i>=1;i--)
        if (c[i]) break;
  c[0]=i;
  return i;
}
int g(int n)
{
  int i,j;
  int temp1[1000],temp2[1000];
  if (GG[n][0]) return GG[n][0];
  if (n==1) {
       GG[1][0]=1;
       GG[1][1]=1;
       return 1;
  }
  memset(temp1,0,sizeof(temp1));
  memset(temp2,0,sizeof(temp2));
  temp2[0]=1;temp2[1]=2;
  temp1[0]=1;temp1[1]=1;
  for(i=1;i<=(n-1)*n/2;i++)
  {
    gjd_mul(temp1,temp2,GG[n]);
    for(j=0;j<=GG[n][0];j++) temp1[j]=GG[n][j];
  }
 return j;
}
int C(int x,int y)
{
  int i,j;
  if (CC[x][y][0]) return CC[x][y][0];
  if ((x==y)||(x==0))
  {
     CC[x][y][0]=1;
      CC[x][y][1]=1;
      return CC[x][y][0];
  }
  C(x,y-1);C(x-1,y-1);
  gjd_add(CC[x][y-1],CC[x-1][y-1],CC[x][y]);
  return CC[x][y][0];
}
int f(int n)
{
  int i,j,k,t,ans,temp[1000],temp1[1000];
  if (FF[n][0]) return FF[n][0];
  memset(temp,0,sizeof(temp));
  g(n);
  gjd_add(temp,GG[n],FF[n]);
  for(i=1;i<=n-1;i++)
  {
    C(i-1,n-1);f(i);gjd_mul(GG[n-i],FF[i],temp1);
     gjd_mul(temp1,CC[i-1][n-1],temp);
    gjd_min(FF[n],temp);
  }
}
int main()
{
  int n,i,j,k;
  memset(FF,0,sizeof(FF));
  memset(GG,0,sizeof(GG));
  memset(CC,0,sizeof(CC));
  while((scanf("%d",&n),n)!=0)
  {
  f(n);
  for(i=FF[n][0];i>=1;i--)
   printf("%d",FF[n][i]);
  printf("/n");
  }
  return 0;
}
中国語の翻訳
1.テーマ
   1つの無方向図は、v個の頂点とe個のエッジ(E∈{V*V})からなる集合である.1つの無方向図が各点対(u,v)に対してuから最後までvを通過できる場合、この図は連通し、あなたの任務は1つのプログラムを書いてn個の頂点を含む連通の無方向図を計算することである.
  次の例のように、3つの頂点を含む連通の無方向図が4つあります.
 
2.説明の入力
  入力は複数のデータ群を含み、各データは整数nを含み、頂点数(1=0を終了フラグとして入力します.
3.出力説明
    テストポイントごとに結果を1行で出力します.