ABC 247 G — Dream Team

考察

大学と得意分野をそれぞれ頂点、人をその間の辺と考えると、選べるチームは端点を共有しない辺集合になる。これは二部マッチングである。人数ごとに強さの合計を最大化したいので、人数を流量、強さを費用へ対応させ、流量別の最小費用を求める。

人数を流量、強さを費用に対応させる

人 jj の大学・分野・強さをそれぞれ Aj,Bj,CjA_j,B_j,C_j とする。始点 SS と終点 TT を用意し、次の辺を張る。

  • SS から各大学へ、容量 1・費用 0 の辺。
  • 人 jj の大学から分野へ、容量 1・費用 BIG−Cj\mathrm{BIG}-C_j の辺。
  • 各分野から TT へ、容量 1・費用 0 の辺。

ここで BIG\mathrm{BIG} は全員の強さより大きい定数とし、例えば 109+110^9+1 を使う。人を選ぶことがその人の辺へ 1 流すことに対応し、大学側と分野側の容量 1 が、それぞれの重複禁止を表す。ii 人のチームに対応する流れの費用は

i BIG−∑j:選んだ人Cji\,\mathrm{BIG}-\sum_{j\text{:選んだ人}}C_j

である。同じ人数なら第一項が共通なので、最小費用を c(i)c(i) とすると、求める強さの最大値は i BIG−c(i)i\,\mathrm{BIG}-c(i) となる。

強い人から順に採用するだけでは足りない。例えば、大学・分野・強さが (1,1,100),(1,2,10),(2,1,1)(1,1,100),(1,2,10),(2,1,1) の 3 人では、1 人の最適解は強さ 100 の人だが、2 人の最適解は残る 2 人で合計 11 となる。人数を増やすとき、既に選んだ人を取り消して選び直す必要がある。最小費用流の残余逆辺は、この取消しを表す。

逐次増加という算法と、ACL の呼出しを区別する

自前で逐次最短路増加法を実装するなら、流量・費用を 0、各頂点の potential を 0 で初期化する。元の辺の費用はすべて非負なので、この初期化で始められる。残余グラフ上で potential を使った最短路を探し、potential と残余容量を更新して 1 流し、累積流量と累積費用を記録する。これらの状態を維持する一つの実行を、増加路がなくなるまで続ければよい。各増加が流量別の最適性を保つ理由と potential の更新式は、主単元の説明を参照する。

一方、ACL の公式仕様では、同じグラフへの flow と slope を合わせた複数回呼出しの挙動は未定義である。「1 ずつ増やす」を、graph.flow(S,T,1) の繰返しとして実装してはいけない。ACL では、辺をすべて追加した未実行のグラフに対し、流量上限を指定しない graph.slope(S,T) を一度だけ呼ぶ。これで最大流までの流量別最小費用が得られる。

ただし、返るのは全人数の値を並べた配列ではなく、最小費用の折れ線の端点列である。同じ限界費用、すなわち 1 流すための費用の増分が続く区間では、同一直線上の中間点が省かれる。

折れ線から全人数の答えを取り出す

返り値の最初の点は (0,0)(0,0) で、最後の点の流量が最大人数 KK である。まず KK を出力する。次に隣り合う端点 (f0,c0),(f1,c1)(f_0,c_0),(f_1,c_1) を順に見て、その区間の単位増加費用

d=c1−c0f1−f0d=\frac{c_1-c_0}{f_1-f_0}

を求める。この区間では限界費用が一定なので、各整数人数 i=f0+1,…,f1i=f_0+1,\ldots,f_1 に対して

c(i)=c0+(i−f0)dc(i)=c_0+(i-f_0)d

を復元し、i BIG−c(i)i\,\mathrm{BIG}-c(i) を出力する。辺費用が整数なので dd も整数であり、浮動小数点計算は不要である。左端を除いて右端を含めることで、区間の境目の人数を二重に出力せず、1 人から KK 人までをちょうど一度ずつ扱える。

例えば、大学も分野も異なる強さ 5 の 2 人を考え、ここだけ BIG=10\mathrm{BIG}=10 とする。最小費用は c(0)=0,c(1)=5,c(2)=10c(0)=0,c(1)=5,c(2)=10 であり、slope は (0,0),(2,10)(0,0),(2,10) だけを返す。区間の傾きは 5 なので、人数 1 の答えは 10−5=510-5=5、人数 2 の答えは 20−10=1020-10=10 と両方復元できる。端点だけを出力すると、人数 1 の答えを落としてしまう。

また、大学の種類数を UU、分野の種類数を FF とすると、min⁡(U,F)\min(U,F) は KK の上界にすぎない。例えば属性対が (1,1),(2,1),(3,2),(3,3)(1,1),(2,1),(3,2),(3,3) なら、大学も分野も 3 種類あるが、最初の 2 大学は分野 1 を取り合うため最大人数は 2 である。実際に流せた最大流量を slope の最後から読み、実現可能な人数だけを出力する。

典型の発動条件

二部 matching の flow 表現

2 種類の属性がそれぞれ重複禁止で、選ぶ要素が属性対を結ぶとき、要素を二部グラフの辺にする。両側に容量 1 の辺を置くと、重複禁止を流量制約へ移せる。

重み付き matching の min-cost flow

人数ごとの最大重みをすべて求めたいとき、人数を流量に対応させる。固定流量のどの選び方にも同じ費用補正が掛かることを確認してから、重みを非負費用へ変換する。slope を使う場合は、圧縮された端点列から必要な全整数流量の値を復元する。

問題固有の要素

大学と分野がそれぞれ重複禁止なので、1 人を二部グラフの 1 辺にできる。ちょうど ii 人なら必ず人の辺を ii 本選ぶため、各辺に BIG\mathrm{BIG} を足す補正も必ず i BIGi\,\mathrm{BIG} になる。

別の問題へ持ち帰る視点: 個数別の最大価値を求めるときは、固定個数で共通になる費用補正と、個数を増やす際の選び直しの両方を考える。

正当性

整数流では、各大学から高々 1 本、各分野へ高々 1 本の人の辺に流れるため、流量 ii の流れは条件を満たす ii 人のチームに対応する。逆に、そのようなチームから各人を通る経路へ 1 ずつ流せる。両者の費用は i BIGi\,\mathrm{BIG} から強さの合計を引いた値なので、流量 ii の最小費用 c(i)c(i) から得る i BIG−c(i)i\,\mathrm{BIG}-c(i) が求める最大値である。

初期流量 0 の残余グラフには負費用閉路がなく、逐次最短路増加法はこの固定流量での最適性を保ちながら流量を増やす。残余逆辺による取消しも許すので、以前のチームを含まない最適チームにも組み替えられる。増加路がなくなると最大流であり、その流量 KK は構成可能な最大人数に等しい。

一度の slope が返す折れ線は、0 から KK までの各流量の最小費用を表す。連続端点間では限界費用が一定なので、線形補間で省略された各整数人数の c(i)c(i) も正確に復元できる。各区間の左端を除き右端を含めて出力すれば、すべての実現可能な人数の答えを漏れ・重複なく出力する。

実装上の注意

  • mcf_graph<int,long long> などを使い、費用・potential・累積費用・i BIGi\,\mathrm{BIG} の積を 64 bit 整数で扱う。BIG=109+1\mathrm{BIG}=10^9+1 ならすべての人の辺費用が正になり、最大 150 人の補正項も 64 bit に収まる。
  • 同じグラフで flow を実行してから slope を呼ぶことも、複数回呼出しに当たる。最大人数の取得と全人数の答えの復元には、一度の slope の結果を共有する。
  • 区間の費用差を流量差で割って整数の傾きを求めてから補間する。端点の個数を最大人数と取り違えず、最後の点の流量を使う。
  • 同じ属性対 (Aj,Bj)(A_j,B_j) の人が複数いても平行辺のままでよい。圧縮するなら、両者を同時には選べず、強い方への置換で人数と制約を保てるため、最大の CjC_j だけ残せる。

復習の核

  • 人数ごとの最適なチームは、人数を増やすと既存の選択を取り消すことがある。残余逆辺による選び直しまで含めて最適化する。
  • 算法の「1 ずつ増やす」と API の「1 を指定して繰り返し呼ぶ」を区別する。ACL では一度の slope を使い、省略された人数の答えを補間する。
  • 属性の種類数は最大人数の上界であり、実際に選べる人数は接続関係で決まる。

計算量と制約

時間

大学 UU 種類、分野 FF 種類、人 NN 人とする。頂点数は V=U+F+2V=U+F+2、追加する辺数は E=U+F+NE=U+F+N で、グラフ構築は O(V+E)O(V+E)。1 回の増加は流量 1 なので、最大人数 KK に対して増加は KK 回となる。ACL の slope の時間計算量は O(K(V+E)log⁡(V+E))O(K(V+E)\log(V+E))、全人数の補間と出力は合計 O(K)O(K) であり、構築を含む全体も O(K(V+E)log⁡(V+E))O(K(V+E)\log(V+E)) となる。ここでは N≥1N\geq 1 より K≥1K\geq 1 を使った。

空間

残余グラフと最短路用の配列が O(V+E)O(V+E)、slope の端点列が O(K)O(K) なので、全体で O(V+E+K)O(V+E+K)。復元した答えは人数順にそのまま出力できる。

制約との対応

公式制約は 1≤N≤3×1041\leq N\leq 3\times 10^4、1≤Aj,Bj≤1501\leq A_j,B_j\leq 150、1≤Cj≤1091\leq C_j\leq 10^9 で、入力はすべて整数である。したがって U,F≤150U,F\leq 150、V≤302V\leq 302、E≤30300E\leq 30300、K≤150K\leq 150 となり、増加回数を小さく抑えられる。K=min⁡(U,F)K=\min(U,F) とは限らないため、人数の出力範囲には実際の最大流量を使う。時間制限は 2 秒、メモリ制限は 1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Dream Team の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小費用流・circulation

主題
  • 最小費用流・circulation: 流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 最小費用流・circulation

      執筆: abc-explanation-author1.1.1 / revision 3

      学習の位置

      体系上の位置: 最小費用流・circulation

      • 流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

      • 最大流・最小カット — 状態グラフのモデリングと探索で得た考え方と実装を再利用し、最大流・最小カットの発動条件・正当化・境界を重複なく学ぶ。
      • 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題