AOJ-ICPC 2016.10.8
解ける問題がなくなってきた。
問題
問題概要
省略
解法
全頂点対に容量0の辺を張っておく。
最初から辺があるものについては容量1にしておき、最大流を求めておく。以下、この残余グラフ上で考える。
追加のクエリが来たら、その辺の容量を1にし、から
に1流した結果を最大流に加える。
削除のクエリが来たら、その辺が使われていなかった場合(容量が1の場合)は容量を0にする。
そうでなければ、削除する辺の
から
に流れているとする。
その辺の容量を0とし、から
に1流す。
流れた場合は別のパスが見つかったということなので、最大流は変わらない。
流れなかった場合は最大流は1減らし、から
、
から
のフローを押し戻す。
これはから
、
から
に1流せばよい。
問題
Alternate Escape | Aizu Online Judge
問題概要
省略
解法
後退解析。
盤面の座標+盤外の頂点のグラフを考える。
辺で隣接関係を表現する。辺の重みは最初に壁があれば、なければ
としておく。
勝ち頂点へ遷移できる頂点は次の2つの条件を満たす頂点である。
・勝ちマスへ辺が張られており、その辺の重みがである。
・勝ちマスへ辺が張られており、その辺の重みがである。
勝ち頂点が増えなくなるまでBFSを繰り返し、初期状態で勝ち頂点にいた場合、勝ちとなる。
コーナーケースとして、一手で盤外に出られる場合は無条件で勝ちとなる。
問題
Deadlock Detection | Aizu Online Judge
問題概要
個のプロセスと
種類のインスタンスがある。
インスタンスは
個ある。
プロセスはインスタンス
を
個要求する。
デッドロックとは、異なるプロセスが互いに必要なインスタンスを占有しているため、プロセスが途中で実行できなくなることである。
デッドロックは適切な順番でプロセスを実行することで回避できる（終了したプロセスが占有しているインスタンスは解放されるため）。
プロセスがインスタンスを要求するログが与えられるので、デッドロックが発生することが確定する時間を求めよ。
