給定一個有權有向圖 \(G=\langle V,A\rangle,w:A\mapsto\mathbb{R}\) 和一個根 \(r\in G\)，求以 \(r\) 為根的最小生成樹，滿足每條邊都是父親指向兒子（外向樹）。

不失一般性，我們可以簡單的 \(O(|V|+|A|)\) \(\text{dfs}\) 判斷這樣的樹是否存在，并且對于平行弧，我們可以只保留較小的那條。

然后我們約定 \(E\subseteq A,w(E)=\sum\limits_{e\in E}w(e)\)。

用 \(\pi(v)\) 表示所有指向 \(v\) 的弧 \(e=(u,v)\) 中 \(w(e)\) 最小的 \(u\)?？紤] \(M=\langle V,\{(\pi(v),v):\forall v\in V\setminus\{r\}\}\rangle\)，如果 \(M\) 中無環，那么 \(M\) 就是所求。

若 \(M\) 中有環，我們考慮遞歸地縮點：

任選一個環 \(C\in M\)。新建節點 \(v_C\)，建立新圖 \(G^\prime=\langle V^\prime,A^\prime\rangle,w^\prime:A^\prime\mapsto\mathbb{R}\)，其中 \(V^\prime=(V\setminus C)\cup\{v_C\}\)。

\(A^\prime\) 滿足，\(\forall e=(u,v)\in A\land e\not\in C\)：

1. \(u,v\not\in C\)，\(e=(u,v)\in A^\prime,w^\prime(e)=w(e)\)；
2. \(u\in C,v\not\in C\)，\(e^\prime=(v_C,v)\in A^\prime,p=(\pi(u),u),w^\prime(e^\prime)=w(e)-w(p)\)；
3. \(u\not\in C,v\in C\)，\(e=(u,v)\in A^\prime,w^\prime(e)=w(e)\)。

用 \(f(G,r)\) 表示圖 \(G\) 中以 \(r\) 為根的最小樹形圖大小，有 \(f(G,r)=f(G^\prime,r)+w(C)\)。

沒有環的情況，正確性是顯然的。

有環的時候，我們其實應該選擇一條進入環的邊，但是我們不知道具體選擇哪一條，但是因為是有向邊，所以從 \((u,v)\) 進入環之后，\((\pi(v),v)\) 這條邊就沒必要選了。不難發現我們恰好需要一條邊來打破一個環，于是就按照上述方法得到 \(w^\prime\) 即可保證貪心的正確性。

按照剛剛講的思路暴力，每輪建立 \(M\) 的代價是 \(O(|V|+|A|)\)，找環的代價也是 \(O(|V|+|A|)\)，然后每次縮點至少減少 \(1\) 個點，至多執行 \(O(|V|)\) 輪。于是整體復雜度就是 \(O(|V|^2+|V||A|)\)，注意到不連通可以 \(O(|V|+|A|)\) 判定，于是可以寫成 \(O(|V||A|)\)（忽略沒有弧的情況）。

我們發現每輪全部重新計算太浪費了，只需要修改環上的點。于是我們用可并堆維護每個點的入邊（如果要做到理論最優，需要 \(\text{fib}\) 堆），再用并查集維護縮點的關系，這樣就可以做到 \(O(|A|+|V|\log|V|)\) 了。

代碼？鴿子能更新就不錯了。