这是楼教主的男人八题之一。很高兴我能做八分之一的男人了。
题目大意：求有n个顶点的连通图有多少个。
解法：
1、 用总数减去不联通的图（网上说可以，我觉得时间悬）
2、 用动态规划（数学递推）。网上讲的方法我觉得非常难懂，但好像也没有更好的表示。我就说一下吧：
用dp[i]表示i个顶点时的连通图的总数。
考虑将1号点去除后，2号点所在的联通块。设此联通块有k个点，则这块共有C（n-2，k-1）种取法。
回过头来看刚开始的图。可以把图分成两块，一是上述联通块，其余的另一块（此块也一定联通），这两块之间至少有一条连线，而这些线段肯定有一个顶点是1号点（用反证法很容易得到）。K个顶点连线到1号点的情况总共有2^k种，去除一种都不连的情况，还剩（2^k）-1种。故此时共有dp[j]*dp[i-j]*((2^k)-1)*C(n-2,k-1)
综上，dp[i]=sigma{ dp[j]*dp[i-j]*((2^k)-1)*C(n-2,k-1)} (1<=j<i)
最后提醒一句，虽然大家都知道：要用高精度
代码：
#include<cstdio>
#include<cstring>
using namespace std;
int max(int x,int y){
return(x>y)?x:y;
}
struct bign{
int len,p[240];
bign(){
len=1;
memset(p,0,sizeof(p));
}
bign operator =(const bign &o){
len=o.len;
memcpy(p,o.p,sizeof(p));
return *this;
}
bign operator +(const bign &o){
bign ans;
ans.len=max(len,o.len)+1;
int g=0;
for(int i=0;i<ans.len;i++){
int x=p[i]+o.p[i]+g;
ans.p[i]=x%10000;
g=x/10000;
}
if(ans.p[ans.len-1]==0)ans.len--;
return ans;
}
bign operator *(const bign &o){
bign ans;
ans.len=len+o.len;
for(int i=0;i<len;i++)
for(int j=0;j<o.len;j++){
ans.p[i+j]+=p[i]*o.p[j];
ans.p[i+j+1]+=ans.p[i+j]/10000;
ans.p[i+j]%=10000;
}
while(ans.p[ans.len-1]==0)ans.len--;
return ans;
}
void print(){
printf("%d",p[len-1]);
for(int i=len-2;i>=0;i--){
if(p[i]<10)printf("000%d",p[i]);
if(p[i]>=10 && p[i]<100)printf("00%d",p[i]);
if(p[i]>=100 && p[i]<1000)printf("0%d",p[i]);
if(p[i]>=1000 && p[i]<10000)printf("%d",p[i]);
}
printf("\n");
return;
}
}dp[51],tmp,c[51][51],two[51];
void init(bign &x){
x.len=1;
memset(x.p,0,sizeof(x.p));
x.p[0]=1;
return;
}
int main(){
int n;
scanf("%d",&n);
init(two[0]);
for(int i=1;i<=50;i++)
two[i]=two[i-1]+two[i-1];
for(int i=0;i<=50;i++)
two[i].p[0]--;
init(c[0][0]);
for(int i=1;i<=50;i++){
init(c[i][0]);init(c[i][i]);
for(int j=1;j<i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
init(dp[2]);init(dp[1]);
for(int i=3;i<=50;i++){
for(int j=1;j<i;j++)
dp[i]=dp[i]+dp[j]*dp[i-j]*two[j]*c[i-2][j-1];
}
while(n!=0){
dp[n].print();
scanf("%d",&n);
}
return 0;
}