Connected Graph

我不是女神ヾ 2022-01-08 00:29 267阅读 0赞

[Connected Graph][]

求n个点的无向联通图数量，\\(n\\leq 50\\)。

### 解 ###

直接无向联通图做状态等于是以边点做考虑，难以去重，考虑联通对立面即不联通。

不难求出n个点的总方案数为\\(2^\{\\frac\{n\\times (n-1)\}\{2\}\}\\)，所以设\\(f\_i\\)表示n个点的无向联通图个数，因此我们有

\\\[f\_i=2^\{\\frac\{n(n-1)\}\{2\}\}-\\sum\_\{j=1\}^\{i-1\}f\_jC\_i^j2^\{\\frac\{(i-j)(i-j-1)\}\{2\}\}\\\]

但是这样的转移存在重复，考虑特殊化去重，注意到如果这张图不合法，可以等价于任何一个联通图不合法，于是可以强制让点1不合法，因此有

\\\[f\_i=2^\{\\frac\{n(n-1)\}\{2\}\}-\\sum\_\{j=1\}^\{i-1\}f\_jC\_\{i-1\}^\{j-1\}2^\{\\frac\{(i-j)(i-j-1)\}\{2\}\}\\\]

边界：\\(f\_1=1\\)

答案：\\(f\_n\\)

时间复杂度显然\\(O(n^2)\\)，但是高精度占去大量时间。

参考代码：

#include <iostream> #include <cstdio> #include <cstring> #define il inline #define ri register #define ll long long using namespace std; struct lll{ int num[1001]; lll(){num[0]=1;} il void clear(){ memset(num,0,sizeof(num)),num[0]=1; } il void read(){ string s;cin>>s,num[0]=s.size(); for(ri int i(1);i<=num[0];++i) num[i]=s[num[0]-i]; } il void print(){ for(ri int i(num[0]);i;--i)putchar(num[i]+48); } il void operator=(string s){ num[0]=s.size(); for(ri int i(1);i<=s.size();++i) num[i]=num[s.size()-i]; } il lll operator+(lll x){ lll y;y.clear();ri int i; for(i=1;i<=num[0]||i<=x.num[0];++i){ y.num[i]+=num[i]+x.num[i]; if(y.num[i]>9)++y.num[i+1],y.num[i]-=10; }y.num[0]=i; while(!y.num[y.num[0]]&&y.num[0]>1)--y.num[0]; return y; } il lll operator-(lll x){ lll y;y.clear();ri int i; for(i=1;i<=num[0];++i){ y.num[i]+=num[i]-x.num[i]; if(y.num[i]<0)--y.num[i+1],y.num[i]+=10; }y.num[0]=i; while(!y.num[y.num[0]]&&y.num[0]>1)--y.num[0]; return y; } il lll operator*(lll x){ lll y;y.clear();ri int i,j,k; for(i=1;i<=num[0];++i){ k=0; for(j=1;j<=x.num[0];++j) y.num[i+j-1]+=num[i]*x.num[j]+k, k=y.num[i+j-1]/10,y.num[i+j-1]%=10; y.num[i+x.num[0]]+=k; }y.num[0]=i+j; while(!y.num[y.num[0]]&&y.num[0]>1)--y.num[0]; return y; } }p2[2501],c[51][51],dp[51]; int main(){ int n,i,j;p2[0]="1"; for(i=1;i<=2500;++i)p2[i]=p2[i-1]+p2[i-1]; for(i=0;i<=50;++i){c[i][0]="1"; for(j=1;j<=i;++j) c[i][j]=c[i-1][j]+c[i-1][j-1]; } while(scanf("%d",&n),n){ memset(dp,0,sizeof(dp)),dp[1]="1"; for(i=2;i<=n;++i){ dp[i]=p2[i*(i-1)>>1]; for(j=1;j<i;++j) dp[i]=dp[i]-dp[j]*c[i-1][j-1]*p2[(i-j)*(i-1-j)>>1]; }dp[n].print(),putchar('\n'); } return 0; }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10987557.html

[Connected Graph]: http://poj.org/problem?id=1737