# 問題定義
給定一個有向圖與一個傳播起點，每一個回合，擁有資料的點 $v$ 可以複製一份資料到點 $u$ (若存在路徑 $v\to u$) 問幾個回合之後所有點都擁有資料。
不失一般性的，假設起點對所有點都有可到達性。且第 $0$ 回合起點有資料。
已知本問題在圖是 DAG 或更複雜結構是 NPC 問題。
## 圖是一條鏈
為了討論方便，將頂點標記為 $v_1, v_2\cdots v_n$ ，且規定 $v_1$ 是唯一的 root，也就是說每一回合僅能將資料從 $v_i$ 傳給 $v_j$ ，若 $i<j$。
很顯然的可以在恰好 $\lceil\log n\rceil$ 個回合完成，並且這是最大化複製沒有浪費的狀況
* 定理1. 任意狀況下，$n$ 個節點最少需要使用 $\lceil\log n\rceil$ 個回合。
因為在第 $n$ 個回合最多只有 $2^n$ 份資料，資料數量必須比點數還要多。
## 完全暴力解
我們考慮傳輸的拓譜網路，由於除了根 $r$ 每一個點僅被最多一個點指入，因此該網路是一棵樹。這裡試圖給出一個最優解，我們枚舉所有可能的拓譜網路，最佳解必然是位在某一個拓譜網路上。
根據 Cayley formula ，$n$ 個點能產生 $n^{n-2}$ 種生成樹。對於枚舉出的生成樹，直接驗證是否合法並加以計算，因此複雜度為
1. 產生所有生成樹 $n^{n-2}$ 種
* 有 $O(n^n)$ 的生成方法
* Algorithms for generating all possible spanning trees of a simpleundirected connected graph (2019) Maumita Chakraborty · Sumon Chowdhury · Joymallya Chakraborty · Ranjan Mehera · Rajat Kumar Pal.
2. 驗證單一生成樹 $O(n)$
故複雜度為 $O(n^n)$
## 動態規劃優化
利用動態規劃來記錄一個集合的最優解，使用 bitset $b=010100_b$ 來表示考慮了哪一些點來計算答案。
因為規定節點只能往編號比較大的方向傳，因此規定
1. $\operatorname{lowbit}(b)$ 是 $b$ 唯一的 root。
* 因為沒有其他點可以給 $\operatorname{lowbit}(b)$
使用 $dp[b]$ 紀錄以 $\operatorname{lowbit}(b)$ 為根的節點集合，最短的傳遞回合樹。
很顯然的，若 $|b|=1$，則 $dp[b]=0$。
若 $b$ 有至少兩個元素，則 $dp[b]$ 為以 $\operatorname{lowbit}(b)$ 作為根，$b'=b-\operatorname{lowbit}(b)$ 作為子樹，考慮 $b'$ 的所有可能的排列狀況下，答案最小的狀況。
$$dp[b]=delay(\operatorname{lowbit}(b))+\max\{i+dp[s_i]:i=1,2,\ldots k\}$$
當中 $s_i$ 是 $b'$ 分解後的第 $i$ 個子樹 ($1\leq i$)。
$b'$ 可能由數個子樹構成，所有可能的子樹排列，相當於將其元素劃分為兩兩不相交的非空子集，該問題的答案為 Bell number。若 $|b'|=n$，其解為 $B_n=\sum\limits_{k=0}^n S(n, k)$，當中 $S(n, k)$ 為第二類斯特靈數， $S(n, k)$ 定義為將 $n$ 求分成 $k$ 個非空不相交集合。
若已知每一個子樹的傳遞花費時間，可以證明根應優先傳遞給花費時間最大的子樹，因此排序子樹的答案即可快速求出，排序的時間不大於 $O(n\log n)$。
設操作長度為 $n$ 的 bitset 需要 $\sigma(n)\in O(n)$ 的時間，因此該動態規劃複雜度
1. 狀態數 ... $O(2^n)$
2. 轉移數 ... $O(B_n)$
3. 轉移成本 ... $O(n\log n+\sigma(n))\in O(n\log n)$
又因 $B_n\leq \left(\frac{0.792n}{\ln {n+1}}\right)^n$
因此複雜度 $O(f(n))$ ，$f(n)$ 為
$2^n\cdot\left(\frac{0.792n}{\ln {n+1}}\right)^n\cdot n\log n\leq\left(\frac{n}{\ln n}\right)^n\cdot 1.584^n\cdot n\log n$
## 更進一步的動態規劃優化
對於直接枚舉所有可能的子樹需要花費的成本遠大於狀態樹十分的不滿意，我們將其修正為枚舉 **第一個子樹** 與剩餘子樹。
同樣的，使用 $s_i$ 來表示分解出的第 $i$ 個子樹，原本的動態規劃想要求
$$dp[b]=delay(\operatorname{lowbit}(b))+\max\{i+dp[s_i]:i=1,2,\ldots k\}$$
也就是
$$dp[b]=delay(\operatorname{lowbit}(b))+\max\{1+dp[s_1], 2+dp[s_2], \cdots ,k+dp[s_k]\}$$
扣除了 $s_1$，與不影響答案的常量 $delay(\operatorname{lowbit(b)})$ 如何求剩餘的 $\max\{2+dp[s_2], \cdots ,k+dp[s_k]\}$ 呢？
經觀察發現
$dp[b-s_1]=\operatorname{lowbit}(b-s_1)+\max\{1+dp[s'_1], 2+dp[s'_2], \cdots ,k'+dp[s'_{k'}]\}$
稍移項調整得
$$dp[b-s_1]-\operatorname{lowbit}(b)+1=\max\{2+dp[s'_1], \cdots ,k'+1+dp[s'_{k'}]\}$$
因為 $s'_1\cup s'_2\cup \cdots \cup s'_{k'}=s_2\cup s_3\cup \cdots \cup s_{k}=b-s_1-\operatorname{lowbit}(b)$，根據 dp 轉移的定義，本 max 表達的定義為：將集合 $b-s_1-\operatorname{lowbit}$ $ 分解數個子樹後，傳輸的的最小回合數，故兩者答案必須相等。 (若不相等則可以用比較小的那一個取代比較大的來更新解答)
得到轉移方程
$$dp[b]=delay(\operatorname{lowbit}(b))+1+\max\{dp[s_1], dp[b-s_1]-delay(\operatorname{lowbit}(b))\}$$
計算 DP 的時間複雜度
1. 狀態數 ... $O(2^n)$
2. 轉移數 ... $O(2^n)$
3. 單次轉移成本 ... $O(\sigma(n))$
* 計算 lowbit 等等
故複雜度為 $$O(4^n\sigma(n))$$
## 更更進一步的優化
如果轉移的枚舉是完美的，也就是對於長度為 $n$ 的 bitset $b$，若當中的元素數量為 $|b|$ ，能洽在 $O(2^{|b|}\cdot \sigma(n))$ 內不多餘的枚舉的話，那麼複雜度為
$$\Theta\left(\sum\limits_{k=0}^{n}\binom{n}{k}2^k\cdot \sigma(n)\right)$$
> 有 $\binom{n}{k}$ 個狀態，每個狀態有 $k$ 個元素，花費的轉移成本是 $2^k$
按二項式定義
$$(1+x)^n=\sum\limits_{k=0}^{n}\binom{n}{k}x^k$$
因此複雜度為
$$\Theta\left(3^n\cdot \sigma(n)\right)$$
#### 完美的子集合枚舉法
不重複不遺漏的枚舉一個二進位子集合，其程式碼表示如下
```cpp
for (int sub = all; sub != 0; sub = (sub - 1) & all) {
// do something for sub
}
```
當中的 ```(sub - 1) & all``` 求的是，在 2 進位表示下小於 sub 的最大集合。
因為 ```sub - 1``` 會將 ```lowbit(sub)``` 設為 $0$，小於 ```lowbit(sub)``` 的 bit 設為 $1$，再利用 ```&all``` 來保證元素皆在集合中。
```
all = 1101101
sub = 1101000
sub-1 = 1100111
all & 1101101
---------------
next 1100101
^ 原來的 lowbit 反轉為 0
^^^ 原來的低位變成 1
再透過 & all 取出所有集合中的元素
```
因此 next 是集合的二進位表示下，小於 sub 中最大的。
## 延伸應用
本解法可以在稍作修改的狀況下，解出下版本的問題
### 圖是 DAG
如果有多個起點，則增加一個超級起點作為新的起點。將圖拓補排序後，將點重新依序編號到一直線上。
對於原來的 $dp[b]$ ，如果以 $\operatorname{lowbit}(b)$ 作為跟無法連通所有點，則 $dp[b]=\infty$。
在切分 $s_1$ 時，額外檢查是否存在邊 $\operatorname{lowbit}(b)\to\operatorname{lowbit}(s_1)$。
其餘結構不變。
### 點 $v$ 傳給 $u$ 有傳輸時間 $t_{v,u}$
把
$$dp[b]=delay(\operatorname{lowbit}(b))+\max\{i+dp[s_i]:i=1,2,\ldots k\}$$
改為
$$dp[b]=delay(\operatorname{lowbit}(b))+\max\{\sum\limits_{j=1}^{i}t_{\operatorname{lowbit}(b),\operatorname{lowbit}(s_j)}+dp[s_i]:i=1,2,\ldots k\}$$
因此轉移方程為
$$dp[b]=delay(\operatorname{lowbit}(b))+t_{\operatorname{lowbit}(b),\operatorname{lowbit}(s_1)}+\max\{dp[s_1], dp[b-s_1]-delay(\operatorname{lowbit}(b))\}$$
## 程式碼實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
int solver(vector<int> delay) {
int N = delay.size();
vector<int> dp(1LL << N, INT_MAX);
for (int all = 1; all <= (1 << N) - 1; ++all) {
int r = all & -all; // lowbit(all)
int root_delay = delay[__lg(r)];
if (r == all) {
dp[all] = 0;
continue;
}
int Sub = all - r;
for (int S1 = Sub; S1; S1 = (S1 - 1) & Sub) {
int Other = all - S1;
if (Other == r) { // no other subtrees
dp[all] = min(dp[all], root_delay + 1 + dp[S1]);
} else {
dp[all] = min(dp[all], root_delay + max(1 + dp[S1], dp[Other] + 1 - root_delay));
}
}
}
return dp.back(); // dp[2**n-1]
}
int main() {
vector<int> delay;
int n;
while (cin >> n) {
delay.resize(n);
for (int i = 0; i < n; ++i)
cin >> delay[i];
cout << solver(delay) << '\n';
}
}
```
Sign in with Wallet
Connect another wallet