題意

給出點數為 $n$（$n \le 1000$）的完全圖 $K_n$，帶邊權。隨機出 $K_n$ 的一棵生成樹 $T$。求 $T$ 上任意兩點間距離的期望。

解法

固定兩點 $u$、$v$（$u \le v$），考慮生成樹 $T$ 上 $u$ 到 $v$ 的路徑 $P_{uv}$。$P_{uv}$ 上的邊可分成三類：

1. $(u, v)$
2. $(u, x)$、$(y, v)$，$x,y \notin \{u, v\}$
3. $(x,y)$，$x, y \notin \{u, v\}$

第1類邊出現在 $P_{uv}$ 上的概率為 $\dfrac{2}{n}$
每個第2類邊出現在 $P_{uv}$ 上的概率為 $\dfrac{1-\dfrac{2}{n}}{n-2}=\dfrac{1}{n}$

考慮第3類邊（對期望）的貢獻。

首先應當注意到，所有第3類邊出現在 $P_{uv}$ 上是等可能的，所以我們只需要求 $P_{uv}$ 上第三類邊的數目的期望 $E(n)$。

用 $f(i)$ 表示 $K_n$ 的所有生成樹中，滿足「$P_{uv}$ 上點數為 $i$（包括兩端點 $u$，$v$）」的生成樹的數目。
我們分 3 步來求 $f(i)$：

1. 固定 $P_{u,v}$，將 $P_{uv}$ 縮成一點 $w$，加上余下的 $n-i$ 個點，就得到一棵 $n-i+1$ 個點的樹 $T'$。

2. 將 $w$ 的度數固定為 $j$，對應的生成樹 $T'$ 的數目 $g(j)$ 的表達式為
   \begin{equation}
   g(j) = \binom{n-i-1}{j-1}(n-i)^{n-i-j} \label{E:1}
   \end{equation}
   $\eqref{E:1}~$式可通過 Prufer 序列與樹的一一對應關系得到。

3. 與 $w$ 相連的 $j$ 棵子樹中的每一棵，在 $T$ 中可以連在 $P_{uv}$ 上的 $i$ 個點中的任意一個，所以我們得到
   $$
   \begin{equation}
   \begin{aligned}
   f(i) &= \mathrm{A}_{n-2}^{i-2}\sum_{j=1}^{n-i} g(j) \cdot i^{j} \\
   &= \mathrm{A}_{n-2}^{i-2}\sum_{j=1}^{n-i} \binom{n-i-1}{j-1} (n-i)^{n-i-j} \cdot i^{j} \\
   &= \mathrm{A}_{n-2}^{i-2}\cdot i \cdot \sum_{j'=0}^{n-i-1} \binom{n-i-1}{j'}(n-i)^{n-i-1-j'} \cdot i^{j'} \\
   &= \mathrm{A}_{n-2}^{i-2} \cdot i \cdot n^{n-i-1} \label{E:2}
   \end{aligned}
   \end{equation}
   $$

從而
$$
\begin{equation}
\begin{aligned}
E(n) &= \frac{\sum\limits_{i=4}^{n} f(i)(i-3)}{n^{n-2}} \\
&= \sum_{i=4}^{n} \frac{\mathrm{A}_{n-2}^{i-2}i(i-3)}{n^{i-1}}
\end{aligned}
\end{equation}
$$

Implementation

#include <bits/stdc++.h>
using namespace std;using DB=long double;const int N=1005;
DB res[N][N];
int a[N][N];DB calc(int n){if(n<=3) return 0;DB pn=1;for(int i=1; i<=n-2; i++)pn*=i, pn/=n;// cout << pn << endl;DB sum=pn*(n-3);for(int i=n-1; i>=4; i--)pn*=n*i, pn/=(n-i)*(i+1), sum+=pn*(i-3);return sum;
}int main(){// int cnt=0;// for(int i=0; i<=1000; i++)//     cnt+=fabs(t[i]-calc(i))>1e-50;// cout << cnt << endl;int n, tot=0;scanf("%d", &n);for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)scanf("%d", a[i]+j), a[i][0]+=a[i][j], tot+=a[i][j];tot/=2;DB x=calc(n);for(int i=1; i<n; i++)for(int j=i+1; j<=n; j++){res[i][j]=(a[i][0]+a[j][0])/DB(n);if(n>=4)    // 注意：n=2 或 3 時，分母為 0res[i][j]+=x*(tot-a[i][0]-a[j][0]+a[i][j])/((n-2)*(n-3)/2);res[j][i]=res[i][j];}for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)printf("%.9Lf%c", res[i][j], j==n?'\n':' ');return 0;
}

轉載于:https://www.cnblogs.com/Patt/p/6568257.html

總結

以上是生活随笔為你收集整理的hihoCoder #1047 Random Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。