ABC 397 G — Maximize Distance

考察

ある0/1 edge割当でshortest distance≥dとは、各vertexへlabel x_v∈[0,d]を与えx_1=0,x_N=dとし、edge u→vがlabelを一つ進める箇所にweight1を置き、二つ以上飛ぶlabel差を禁止するcut問題として表せる。 距離dを達成するために必要な最小weight1辺数がK以下なら、残りedgeも1へ変えても距離は減らないのでexactly Kを満たせる。 y_{v,j}=1 iff x_v≥jとするとy_{v,j+1}=1,y_{v,j}=0をINF edgeで禁止して整数labelを表す。 edge(u,v)について同levelの0→1 cutにcost1を置き、x_v≥x_u+2をINF制約で禁止すると、選ぶべきweight1辺数とcut costが一致する。

採用する候補: 距離dのlayered binary variablesをs-t min-cutへ帰着し、dを二分探索する

label x_vをthreshold bits y_{v,j}へ展開すると単調性とedge制約がdirected cut edgeになり、O(Nd)頂点graphのmin-cutで必要edge最小数を求められる。

棄却する候補: K本のedge subsetを列挙して0-1 BFSする

C(M,K)通りでM≤100でも巨大で、距離下界というglobal条件を直接扱えない。

d候補ごとにNd threshold nodeを作り、vertex内単調INF edge、元edge由来cost1/INF edge、x_1=0,x_N=dのsource/sink固定を張る。max-flow=min-cutがK以下か判定し、最大dをbinary searchする。

cutのsource側をy=1、sink側をy=0と決める。頂点(v,j)は1≤j≤dで作り、次の有向辺を張る。

役割辺容量・範囲
thresholdの単調性(v,j+1)→(v,j)INF、1≤j<d
元辺u→vの一段上昇の費用(v,j)→(u,j)1、1≤j≤d
元辺u→vの二段以上の上昇禁止(v,j+1)→(u,j)INF、1≤j<d
x_N=dsource→(N,j)INF、1≤j≤d
x_1=0(1,j)→sinkINF、1≤j≤d

例えばx_u=1なら、x_v=1では辺はcutを跨がない。x_v=2ではj=2の容量1辺だけが跨ぐ。x_v=3ではj=2のINF辺も跨いで禁止される。x_v<x_uの辺も費用0でよい。元辺とcutの費用辺は向きが逆になる点に注意する。

典型の発動条件

multi-label submodular problemのgraph cut

発動条件: ordered label差にconvex/禁止costがあり最小化したいとき。

labelをthreshold binary列へ展開してcutへ変換する。

答え二分探索

発動条件: 達成目標dを上げるほど必要resourceが非減少なとき。

必要edge数≤Kを判定する。

問題固有の要素

shortest distanceを直接最大化せず、各vertexのdistance labelがedgeごとに満たすべき局所不等式へ翻訳するとmin-cutになる。

別の問題へ持ち帰る視点: 最短路を悪化させる設計問題では、distance potentialを変数にしてedge constraint違反costを最小化する双対的視点を持つ。

正当性

整数labelの増分を1以下へ制限し、labelが一段増える元edgeだけweight1費用をcutへ課すとpathのtelescopingより1→N距離≥d。逆に任意0/1重み距離からcapped距離labelを作れば同制約とcost上界を満たす。必要one数≤Kなら余りをoneへ増やしても距離が減らずexactKを実現する。

実装上の注意

  • INFはKまたはMを確実に超える値にし、x_1=0,x_N=d固定方向を確認する。d=0と最大N-1の探索境界を扱う。

復習の核

  • N≤7,M≤12で全K-edge subsetと0-1 shortest pathを列挙し、各dのmin-cut値・exact K補完を比較する。

計算量と制約

時間

元N頂点M辺、試行距離d≤N−1。threshold graph V=Nd+2,E=O((N+M)d)。一般Dinic判定O(V²E)、二分探索O(log N)回。

空間

一判定network O((N+M)d)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 30; 1 \leq K \leq M \leq 100; 1 \leq u_j, v_j \leq N; u_j \neq v_j; In the given graph, vertex N is reachable from vertex 1.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Maximize Distance の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最大流・最小カット

主題
  • 最大流・最小カット: 選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 最大流・最小カット

    補助タグ: 単調境界探索

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

    学習の位置

    体系上の位置: 最大流・最小カット

    • 選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 単調境界を証明して探索する — 判定結果が一方向に変わることを証明し、巨大な値域から成功・失敗の境界を二分探索で求める。
    • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題