考察
A→…→B→…→C の単純路は、B から A と C へ向かう二本の path が B 以外で頂点を共有しないことと同値である。辺素な二路では不十分で、共有禁止対象は頂点なので、各頂点へ容量1を課す vertex splitting が必要になる。source→B_out だけ容量2、A_out/C_out→sink は各1、他頂点の in→out を1にすれば、終点も異なる二本を要求できる。無向辺 {u,v} は u_out→v_in と v_out→u_in に変換し、flow decomposition から元 graph の内部頂点素な path を復元できる。
採用する候補: 各頂点を in/out に分け容量1の辺で結び、B から A,C へ合計2流す最大流判定を行う。
整数流は二本の path に分解でき、頂点容量により B 以外の共有を正確に禁止できる。流量上限2なので実質 O(N+M) である。
棄却する候補: BFS で B→A の一本を取り、その内部頂点を削除して B→C を探す。
最初に選んだ path が別の選択可能な二路を塞ぐことがあり、任意の一経路を固定する貪欲は完全でない。
2N+2 頂点の network を作る。各 v に v_in→v_out 容量1(B は source から B_out へ容量2)、各無向辺を両方向の out→in 容量1で張る。A_out,C_out から sink へ容量1を張り、max flow が2なら Yes、未満なら No とする。
典型の発動条件
vertex-disjoint paths の最大流帰着
発動条件: 複数 path が端点以外の頂点を共有しない条件を判定するとき。
vertex splitting の内部辺へ容量1を置き、各 path を単位 flow とする。
単純路の中心分割
発動条件: 指定三頂点を順に通る一つの単純路の存在を問うとき。
中央頂点で二本に分け、内部頂点素という同値条件へ変える。
問題固有の要素
求める一つの path を直接構築するより、B を source とする二 commodity が同じ単一 commodity flow として扱える。
別の問題へ持ち帰る視点: 順序付き指定点 path は中央で切り、disjoint paths の標準帰着が使えないか見る。
正当性
整数flow2はBからA,Cへの二pathへ分解できる。B以外のvertex容量1が共有を禁じ、sink辺各1が別の終点を強制する。二pathを逆と順に結べばBを通るA–C simple pathであり、逆変換も可能。
実装上の注意
- B の容量だけ2を許し、A/C の sink 辺は別々に1とする。無向辺を両向きに張った残余辺と混同しない。
復習の核
- edge-disjoint と vertex-disjoint を区別し、共有禁止箇所に容量を置く。max flow 2から元の二路へ戻せることまで確認する。
計算量と制約
時間
N頂点M辺、流量上限2。二回augment BFS/DFSで O(N+M)。
空間
split graphと残余辺 O(N+M)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 2\times 10^5; N-1\leq M\leq\min\left(\frac{N(N-1)}{2},2\times 10^5\right); 1\leq A,B,C\leq N; A, B, and C are all distinct.; 1\leq U_i<V_i\leq N; The pairs (U_i,V_i) are all distinct.; All input values are integers.
出典