问题描述:

问你包含$n$个节点的无向联通图有多少个,其中节点的编号为$1-n$

输入:

有多组数据,输入以0结束
每组数据一个整数$n$表示有$n$个节点($n<=50$)

输出:

每组数据一行,表示有$n$个节点的无向联通图的个数

思路:

计数类DP好难啊。。。根本想不到。。。

我们设$f[i]$为:包含$i$个节点的无向联通图的个数,那么答案就是$f[n]$。然后这个可以等价为所有无向图总数-无向不联通图的个数。无向图总数很容易求,为$2^{n*(n-1)/2}$,而无向不联通图的个数可以通过DP得到。

假设我们推出了$f[1]$到$f[i-1]$,我们现在要求包含$i$个节点的无向不联通图个数。我们设1号节点所在的联通大小为$j$,那么这个联通块就有$C_{i-1}^{j-1}$种选择节点的方案,对于每一种选择方案,联通块有$f[j]$种构成方法,并且联通块之外的点是可以任意连边的的,所以有$2^{(i-j)*(i-j-1)/2}*f[j]$种情况。于是最后我们可以得出转移方程:
$$f[i]=2^{i*(i-1)/2}-\sum_{j=1}^{i-1} 2^{(i-j)*(i-j-1)/2}*f[j] $$

最后也是最最毒瘤的一点就是这道题要用高精!!!

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define MAXN 2505
#define LL long long
using namespace std;

int n;
string f[MAXN], pow[MAXN];

string add(string x, string y)
{
    string ans;
    int lenx=x.length(), leny=y.length();
    int numx[500]={0}, numy[500]={0};
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxl=max(lenx, leny);
    for(int i=0; i<maxl; i++)
    {
        numx[i]+=numy[i];
        numx[i+1]+=numx[i]/10, numx[i]%=10;
    }
    if(numx[maxl]) maxl++;
    for(int i=maxl-1; i>=0; i--) ans+=numx[i]+'0';
    return ans;
}

string sub(string x, string y)
{
    string ans;
    int lenx=x.length(), leny=y.length();
    int numx[500]={0}, numy[500]={0};
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxl=max(lenx, leny);
    for(int i=0; i<maxl; i++)
    {
        numx[i]-=numy[i];
        if(numx[i]<0) numx[i]+=10, numx[i+1]--;
    }
    while(numx[--maxl]==0 && maxl>0) ;
    for(int i=maxl; i>=0; i--) ans+=numx[i]+'0';
    return ans;

}

string mul(string x, string y)
{
    string ans;
    int numx[500]={0}, numy[500]={0}, numz[500]={0};
    int lenx=x.length(), leny=y.length();
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxlen=lenx+leny-1;
    for(int i=0; i<lenx; i++)
        for(int j=0; j<leny; j++) numz[i+j]+=numx[i]*numy[j];
    for(int i=0; i<maxlen; i++) numz[i+1]+=numz[i]/10, numz[i]%=10;
    if(numz[maxlen]) maxlen++;
    for(int i=maxlen-1; i>=0; i--) ans+=numz[i]+'0';
    return ans;
}

string div(string x, LL b)
{
    string ans;
    int lenx=x.length(), d=0;
    for(int i=0; i<lenx; i++)
    {
        ans+=(d*10+x[i]-'0')/b+'0';
        d=(d*10+(x[i]-'0'))%b;
    }
    for(int i=0; i<ans.size(); i++)
        if(ans[i]!='0') return ans.substr(i);
    return "0";
}

string change(LL x)
{
    string ans;
    int numx[500], lenx=0;
    while(x)
    {
        numx[lenx++]=x%10;
        x/=10;
    }
    for(int i=lenx-1; i>=0; i--) ans+=numx[i]+'0';
    return ans;
}

string comb(LL n, LL m)
{
    string sum="1";
    for(LL i=m+1; i<=n; i++) sum=mul(sum, change(i));
    for(LL i=1; i<=n-m; i++) sum=div(sum, i);
    return sum;
}

int main()
{
    pow[0]="1";
    for(int i=1; i<=1500; i++) pow[i]=mul(pow[i-1], change(2));
    for(int i=1; i<=50; i++)
    {
        f[i]=pow[i*(i-1)/2];
        for(int j=1; j<i; j++)
        {
            string temp="";
            temp=mul(mul(comb(i-1, j-1), f[j]), pow[(i-j)*(i-j-1)/2]);
            f[i]=sub(f[i], temp);
        }
    }
    while(scanf("%d", &n) && n) cout<<f[n]<<'\n';
}

发表评论

邮箱地址不会被公开。 必填项已用*标注