Educational Codeforces Round 34 G. Yet Another Maxflow Problem

バチャでやってて結構面白かったので。

Problem - G - Codeforces

問題概要

以下のように構成される、頂点数 $2n$ ・辺数 $2(n-1)+m$ の有向グラフを考える。

頂点は $n$ 個ずつの2グループに分類され、それぞれAパート・Bパートと呼ぶ。頂点を $A_{1}, ..., A_{n}$ 、 $B_{1}, ..., B_{n}$ と表記する。
$1 \le i \lt n$ について、 $A_{i}$ から $A_{i+1}$ に伸びる容量 $x_{i}$ の辺と $B_{i}$ から $B_{i+1}$ に伸びる容量 $y_{i}$ の辺が存在する。
それらに加えて、Aパートに属する頂点からBパートに属する頂点に伸びる辺が $m$ 本与えられる。

このグラフについて $A_{1}$ を始点、 $B_{n}$ を終点とする最大流量を求めたい。初期状態および以下のようなクエリを順に $q$ 個処理したそれぞれの時点において、この最大流量を求めよ。

整数 $v, w$ が与えられる。 $A_{v}$ から $A_{v+1}$ に伸びている辺の容量を $w$ に変更する。

制約

$2 \le n, m \le 2\times 10^{5}$
$0 \le q \le 2\times 10^{5}$
与えられる辺は問題概要に記した条件を満たし、容量は $1$ 以上 $10^{9}$ 以下

解法

最大流量を求める貪欲アルゴリズム

説明の都合で呼び名がほしいので、Aパートの頂点からBパートの頂点に向かう辺のことを「AB辺」と呼ぶことにします。

クエリ対応は後で考えるとして、まずはあるグラフの状態についての最大流量の求め方を考えます。今回のグラフの構成から、最大流は以下のように求めることができます。

まず、 $A_{1}$ から直接伸びるAB辺でBパートに行くようなフローを流せるだけ流す。
次に、 $A_{1} \to A_{2}$ と流れ、 $A_{2}$ から伸びるAB辺でBパートに行くフローを流せるだけ流す。
...
最後に、 $A_{1} \to \cdots \to A_{n}$ と流れ、 $A_{n}$ から伸びるAB辺でBパートに行くようなフローを流せるだけ流す。

つまり $A_{1}$ になるべく近いところから伸びるAB辺から貪欲に流せるだけ流していくことで、全体の最大流量を求めることができます。

その正当性はFord-Fulkersonのアルゴリズムの動作から証明することができます。Ford-Fulkersonは流量が増加するパスを好きに選んで流せるだけ流すことを繰り返して良い、ただし既にフローを流している辺を逆流して相殺する可能性は考慮すること、というアルゴリズムです。

先ほどの貪欲アルゴリズムの動きを追ってみます。 $A_{i}$ から伸びるAB辺を考える時に既に使われている辺は、 $A_{i}$ 以前を始点とする辺とBパート内部の辺だけです。これらの辺は逆流しても得をしません。Bパート内部だけを逆流することに全く意味はないですし、Aパート側に戻ったとしてもその後に結局 $A_{i}$ に戻ってくることになります（Aパートに戻った後に $A_{i}$ より手前でBパートに移りゴールするようなパスがあるなら、そのパスはとっくに使われているはずです）。

f:id:betrue12:20200222014137p:plain

つまり既に流したフローを逆流することは考えなくて良いため、先ほどの貪欲が正しく動作することが分かります。

Aパート内部の辺容量を無限大として前計算

Aパート内部の辺容量はクエリで変わってしまうので、それに依存しない値を前計算して活用できないでしょうか。具体的には、まずAパート内部の辺容量を全て無限大と仮定してしまいましょう。この状態で先ほどの貪欲法を考え、どれだけフローを流せるかを計算します。求めたいフローは、こうして求めたフローのうちの一部がAパート内部で「詰まった」ような形になります。

$A_{1}, ..., A_{n}$ と順番に、これらから伸びるAB辺を用いたフローを考えます。 $A_{i}$ から $B_{j}$ に伸びるAB辺を用いて流せる最大流量は、このAB辺の容量と $B_{j}$ から $B_{n}$ までに通る辺全ての残容量の最小値になります。これはBパート内部の辺容量をセグメント木で管理しておけば、最小値を求める処理は区間min、実際に容量を使ってフローを流す処理は区間addで計算できます。

これを前から貪欲に行い、 $A_{i}$ から伸びるAB辺で流せた合計流量を $L_{i}$ と書くことにします。こうするとグラフは結局、以下のようなものと同一視できることになります。

f:id:betrue12:20200222014151p:plain

クエリの処理方法

では実際にAパート内部の辺容量が有限である場合の計算方法を考えます。このとき先ほど求めた流量が、Aパート内部が「詰まる」ことにより流せなくなってきます。つまり先ほど求めた $L_{1}, ..., L_{n}$ を前からフロー1単位ずつ見たときに、その途中までを流せるということになります。

f:id:betrue12:20200222014556p:plain

では、ある整数 $k$ について $L_{1}, ..., L_{k}$ が全て流しきれるような条件は何でしょうか。Aパート内部の辺容量と各流量が満たすべき条件を整理しましょう。

f:id:betrue12:20200222021346p:plain

$L_{1}, ..., L_{i}$ までを全て流した上で、 $A_{i} \to A_{i+1}$ の辺に流せる流量を $X_{i}$ とします。これは1つ上で余った流量とこの辺の容量の最小値、つまり $\min(x_{i}, X_{i-1} - L_{i})$ と計算できます。これが $L_{i+1}$ 以上であれば $L_{i+1}$ が全て流せることになります。

この $X_{i}$ を順次展開していくと、結局 $L_{k}$ が全て流せる条件は

$i = 1, ..., k-1$ の全てについて、 $x_{i} - L_{i+1} - L_{i+2} - \cdots - L_{k-1} \ge L_{k}$ が成り立つこと

となり、これはさらに $L_{i}$ の累積和 $S_{i} = L_{1} + \cdots + L_{i}$ を用いると

$i=1, ..., k-1$ の全てについて、 $x_{i} + S_{i} \ge S_{k}$ が成り立つこと

と簡潔に表現することができます。

この条件を満たす最大の $k$ は、 $x_{i} + S_{i}$ をセグメント木で管理しておくことで二分探索で求めることができます。そのような $k$ を求めることができれば、あとは $A_{k+1}$ から流せるフローを $L_{k+1}$ のうちどれだけ流せるかを計算して足すことで答えを求めることができます。