SRM721 Lv3 : Apocalypse
作成日：2017.09.28
最終更新日：2017.09.28
問題概要
$0$から$n-1$まで番号が付けられた$n$個の頂点と、頂点$(i+1)$と頂点$p_i$$(0 \leq i < n-1)$を結ぶ辺からなる木がある。
はじめは$position$に含まれる頂点にコマと爆弾が置いてある。
爆弾は$t$ターン後に爆発し、爆弾の置かれている頂点にあるコマを破壊する。
各ターンにはすべてのコマをそれぞれ1回まで動かすことができる。
あるコマを動かす先の頂点は、今コマがある頂点と辺で結ばれていてコマが置かれていない状態でなければならない。
爆弾が爆発した時に破壊されないコマを最大化した時の数を求めよ。
制約
$2 \leq n \leq 50$
$0 \leq p_i \leq i$
$1 \leq t \leq 50$
考え方
まず$t = 1$の時を考える。
この時は初めにコマが置かれている頂点と辺で結ばれている置かれていない頂点の組を重複しないように最大化することになる。
これは二部グラフの最大マッチング問題であるから最大流問題として解くことができる。
次に$t = 2$の時を考える。
これは各コマにおいて1ターン後の頂点を選んだ後、そこにコマがあるとして$t = 1$の問題を解けば良い。
$t = 1$の問題は最大流問題として解くが、この時コマがある頂点には容量$1$のフローの辺を始点から張ることになる。
つまりコマがあるとした頂点にだけ流量$1$のフローが流れ込むようにすれば良いということである。
よってはじめの1ターンのコマの動かし方もフローで表すことで、全体の問題も最大流問題として解くことができる。
以上を繰り返すことで、辺の数が$O(nt)$、最大流が高々$n/2$のネットワークが構築される(具体的には「解法まとめ」を参照のこと)。
このネットワークの最大流を求めるのはEdmonds-Karp法で十分高速である。
ソースコード
マクロ等はこちら
Edmonds_Karp<T>
void put(int a , int b , T c)
始点$a$、終点$b$、容量$c$の辺をグラフに追加
T ans(int s , int t)
$s$を始点、$t$を終点とする時のグラフの最大流を取得
const int MC = 55;
class Apocalypse {
Edmonds_Karp<int> solve;
bool b[MC];
public:
int maximalSurvival(vector<int> p, vector<int> position, int t) {
int n = p.size() + 1;
for(auto u : position) b[u] = 1;
repp(i,0,t){
solve.put(n*i*2,n*(i*2+1),1);
solve.put(n*(i*2+1),n*(i*2+2),1);
repp(j,1,n){
solve.put(n*i*2+j,n*(i*2+1)+p[j-1],1);
solve.put(n*i*2+p[j-1],n*(i*2+1)+j,1);
solve.put(n*i*2+j,n*(i*2+1)+j,1);
solve.put(n*(i*2+1)+j,n*(i*2+2)+j,1);
}
}
repp(i,0,n){
if(b[i]) solve.put(n*(t*2+1),i,1);
else solve.put(n*t*2+i,n*(t*2+1)+1,1);
}
return solve.ans(n*(t*2+1),n*(t*2+1)+1);
}
};解法まとめ
$i$ターン後の頂点$j$を表す頂点を$(i,j)$とし、張る辺の容量はすべて$1$とする。
$(i,j)$から$(i+1,k)'$には頂点$j,k$が辺で結ばれているか$j=k$の時にのみ辺を張る。
前者はコマが移動すること、後者はコマが移動しないことを表す。
そして、各頂点に高々1個のコマしか存在しないことを保証するために$(i+1,j)'$から$(i+1,j)$に辺を張る。
また始点からは$(0,j)$に、終点へは$(t,j)$から辺を張る。
以上のネットワークの最大流が答えである。(9-25行)