problem

luogu-P3343

solution

$dp(i):$ 當(dāng)恰好加入第 $i$ 小邊時(shí)候，所有點(diǎn)聯(lián)通的方案數(shù)。

則 $ans={\sum }_i\frac{d{p}_i}{\left(\genfrac{}{}{0ex}{}{m}{i}\right)}\frac{i}{m+1}$ 。

重點(diǎn)是如何計(jì)算出 $dp(i)$。

這個(gè)恰好的限制不好搞。加第 $i$ 小的邊之前不能提前聯(lián)通，加后一定要聯(lián)通。

轉(zhuǎn)化一下，$dp(i)=$ 加之前不連通的方案數(shù) $?$ 加之后不連通的方案數(shù)。

記 $f(s,i):s$ 點(diǎn)集中的點(diǎn)之間連了 $i$ 條邊后 $s$ 中的點(diǎn)仍然不連通的方案數(shù)。

記 $g(s,i):s$ 點(diǎn)集中的點(diǎn)之間連了 $i$ 條邊后 $s$ 中的點(diǎn)聯(lián)通的方案數(shù)。

顯然 $f(s,i)+g(s,i)=\left(\genfrac{}{}{0ex}{}{cnt(s)}{i}\right)$，其中 $cnt(s):$ 點(diǎn)集 $s$ 中的點(diǎn)之間的邊數(shù)。

轉(zhuǎn)移枚舉 $s$ 的子集 $t$，滿足 $s\&(?s)$，即 $s$ 中最小元素點(diǎn)也在 $t$ 集合內(nèi)。
$$f(s,i)=\sum _{(s\&?s)\in t?s}\sum _{j=0}^{i}g(t,j)\left(\genfrac{}{}{0ex}{}{s\oplus t}{i?j}\right)$$
這種轉(zhuǎn)移相當(dāng)于以 $s$ 中最小元素點(diǎn)為參考，其所在的聯(lián)通塊為 $t$，其余看作不連通，且 $\left(\genfrac{}{}{0ex}{}{s\oplus t}{i?j}\right)$ 任意選的邊連出來(lái)的集合一定不與 $t$ 有邊相連。這樣就不會(huì)算重了。

最后 $d{p}_i=f(\{1,2,...,n\},i?1)?f(\{1,2,...,n\},i)$。

在代碼實(shí)現(xiàn)中統(tǒng)計(jì)答案略有不同，我是將這個(gè)式子稍微展開(kāi)了一下。
$$ans=\sum _{i=1}^m\frac{i}{m+1}\frac{f(\{1,2,...,n\},i?1)?f(\{1,2,...,n\},i)}{\left(\genfrac{}{}{0ex}{}{m}{i}\right)}$$
考慮相鄰兩位：
$$\begin{gathered} \frac{i}{m+1}\frac{f(\{1,2,...,n\},i?1)?f(\{1,2,...,n\},i)}{\left(\genfrac{}{}{0ex}{}{m}{i}\right)} \\ \frac{i+1}{m+1}\frac{f(\{1,2,...,n\},i)?f(\{1,2,...,n\},i+1)}{\left(\genfrac{}{}{0ex}{}{m}{i+1}\right)} \end{gathered}$$
將 $\frac{1}{m+1}$ 提出來(lái)，發(fā)現(xiàn) $i??f(\{1,2,...,n\},i)$ 且 $(i+1)?+f(\{1,2,...,n\},i)$，相加其實(shí)就是加入了一次 $f(\{1,2,...,n\},i)$。

而 $f(\{1,2,...,n\},m)=0$，不可能所有邊都加完了還不聯(lián)通。

所以，有：
$$ans=\frac{1}{m+1}\sum _{i=0}^m\frac{f(\{1,2,...,n\},i)}{\left(\genfrac{}{}{0ex}{}{m}{i}\right)}$$

code

#include <bits/stdc++.h> using namespace std; #define double long double #define int long long int n, m; int cnt[1 << 10]; double c[50][50]; int f[1 << 10][50], g[1 << 10][50]; struct node { int u, v; }E[50];signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= m;i ++ ) scanf( "%lld %lld", &E[i].u, &E[i].v );for( int s = 0;s < (1 << n);s ++ )for( int i = 1;i <= m;i ++ )if( (s >> E[i].u - 1 & 1) and (s >> E[i].v - 1 & 1) )cnt[s] ++;for( int i = 0;i <= m;i ++ ) {c[i][0] = c[i][i] = 1;for( int j = 1;j < i;j ++ ) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];}for( int s = 0;s < (1 << n);s ++ )for( int i = 0;i <= cnt[s];i ++ ) {for( int t = s;t;t = (t - 1) & s )if( t & (s & -s) )for( int j = 0;j <= min( cnt[t], i );j ++ )f[s][i] += g[t][j] * c[cnt[s ^ t]][i - j];g[s][i] = c[cnt[s]][i] - f[s][i];}double ans = 0;for( int i = 0;i <= m;i ++ ) ans += 1.0 / (m + 1) * f[(1 << n) - 1][i] / c[m][i];printf( "%Lf\n", ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[ZJOI2015] 地震后的幻想乡（状压dp + 期望）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。