POJ - 1737 Connected Graph(计数DP)
设i个点的连通块个数为F(i),所有i个点的图的个数为G(i)
从反面考虑问题,发现i个点连通图个数=所有i个点的图的个数-i个点非连通图的个数。
考虑所有i个点的图的个数,每条边可选可不选,共i×(i−1)/2条边,则G(i)=2i×(i−1)/2
考虑i个点非连通图的个数,设节点1所在的连通块大小为j,那么我们选出这个连通块的方法数为F(j)×Ci−1j−1,也就是从剩下i−1个节点中选出j−1个,与节点1组成连通块。
剩下i−j个点随便乱连,有G(i−j)种搞法。
那么我们可以推出dp方程式:
F(i)=G(i)−∑F(j)×Ci−1j−1×G(i−j)(1≤j≤i−1)
代码(高精自己打)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| bign C[51][51]; inline void Init(){ for (register int i=1;i<=50;++i){ C[i][0]=1,C[i][i]=1; for (register int j=1;j<i;++j){ C[i][j]=C[i-1][j-1]+C[i-1][j]; } } } inline bign pow2(int k){ bign ans=1,p=2; while (k){ if (k&1) ans=ans*p; p=p*p; k>>=1; } return ans; } bign dp[51]; inline bign f(int x){ return pow2(x*(x-1)/2); } int main() { Init(); dp[1]=1; for (register int i=2;i<=50;++i){ dp[i]=f(i); for (register int j=1;j<=i-1;++j){ dp[i]=dp[i]-dp[j]*C[i-1][j-1]*f(i-j); } } while (true){ int x; scanf("%d",&x); if (x==0) break; cout<<dp[x]<<endl; } }
|