天天看點

求最長反鍊 || Dilworth 定理

Dilworth 定理,DAG 中最長反鍊的大小 = 最小路徑覆寫數

構造方案:拆出的 \(x_{in}\) 與 \(x_{out}\) 均在最大獨立集中則選中 \(x\)

$$\Huge \text{Goodbye OI}$$