候補の整列とチェーン
各モジュールの候補を性能の昇順に並べ、整列後の性能と消費量を bi,j,ci,j とする。性能と消費量の組を崩さずに整列する。
di,k=bi,k+1−bi,k
モジュール i に Ai−1 個の頂点 v を作り、, とする。 が始点側にあることは、選んだ候補の番号が より大きいことを表す。各 について、逆向きの辺 の容量を無限大にする。有限容量のカットでは始点側の頂点が接頭部分となり、順方向のチェーン辺がちょうど 本切れる。 の場合も の辺 本で表せる。
積の分解
鉱山のモジュールを入力順に u,v とし、選んだ性能を Bu,Bv とする。
−BuB
最後の項は ∑k,ldu,kd である。各 , について、 に容量 の辺を追加する。増分が の辺は省略してよい。同じ組のモジュールを使う鉱山も個別に処理する。
単項費用と答えの復元
αi=
K=1+max(0,i,jmax(−q
各 1≤j≤Ai について、順方向の辺 vi の容量を とする。この値は正である。候補の選択と有限カットは一対一に対応する。カット容量は純利益の符号を反転した値に を加えた値なので、最小カットを求めればよい。
answer=MK−mincut−k=1∑
数値範囲と計算量
答えは −49998 以上 999999998 以下である。αi≤10, , , が成り立つ。鉱山 個の罰則容量の合計は である。有限容量の総和は 未満なので、無限大として を使える。すべての演算は符号付き ビット整数に収まる。
頂点数は V≤452、追加する辺数は E≤82000 である。残余逆辺は別に保持する。Dinic 法の一般的な時間計算量は O(V2E)、空間計算量は である。
サブタスク
サブタスク 1 では候補の組合せを全列挙する。時間計算量は O((N+M)∏iAi) で、組合せは最大 個である。サブタスク 2 では各モジュールの二択を最大 個の頂点で表す最小カットを使う。サブタスク 3 では完全なチェーンを使う。別の正解コードでは による閾値展開を実装し、構成を照合する。
Solution written by GPT6