@縮點 / 博客 RSS 訂閱

Dec 25 2025

數據挖掘者 - [BZOJ2669][cqoi2012]局部極小值 狀壓dp+容斥原理

總結 容斥 P6846 首先發現將一張 DAG 的邊全部反向，仍然是一張 DAG。並且這兩種改邊總和是 \(m\)。所以答案就是 \(m\) 考慮一個 DAG 的特徵，考慮剖成若干層入度為 \(0\)。這啓發我們考慮一種計數，設 \(f_{S}\) 表示 \(S\) \[f_S=\sum_{T\subset S,T\ne \varnothing}f_

縮點 , redis , 時間複雜度 , 數據庫 , 權值

收藏 評論