TopCoder SRM 721 Div1 Hard (Div2 Hard): Apocalypse

するめうめ

tsutaj.hatenablog.com

問題概要

頂点からなる木がある。

このうち 個の相異なる頂点に、ルークと爆弾が つずつ置かれている。ルークは ステップで隣接した頂点に移動させることができる。

ステップを終えた後に爆弾と同じ頂点にいるルークは、爆発に巻き込まれてしまう。以下の条件を満たしながらルークを ステップ動かすとき、爆発から救えるルークの個数の最大値を求めよ。

• (Div 2) ステップ終えた時点で、同じ頂点に つ以上のルークがあってはならない
• (Div 1) それぞれのステップを終えた時点で、同じ頂点に つ以上のルークがあってはならない

解説

それぞれの頂点について置けるルークが高々 個までという制約がついています。今回の問題は、置ける個数を流量としたとき、フローで解くことができます。

Div 2

グラフの頂点を倍加し、 部グラフにすることを考えます。 ステップで頂点 から に行けるとき、左側の頂点集合で に相当する頂点から、右側の頂点集合で に相当する頂点に向けて容量 の辺を張ります。

次に、source から辺を張ることを考えますが、これは最初にルークがある場所から順次移動するため、 source から (最初にルークがある頂点) に向けて容量 の辺を張ります。

そして sink に辺を張ることを考えますが、これは最終的に生き残れる場所 (爆弾のない場所) にルークがいれば、生き残るルークの数が増えていき、そこに存在できるルークは高々 つであるので、 (最後にルークがいたら生き残れる頂点) から sink に向けて容量 の辺を張ります。

これの source から sink への最大流を求めることで、答えを出すことができます。

Div 1

Div 1 では、Div 2 の制約に加えて、「各ステップで」同じ頂点に存在できるルークの数が高々 という制約があります。

これは各ステップにおいて頂点の流量制約が までであると捉えると、頂点数を 倍して、「時間 から にかけて頂点 から へと移動可能であり、頂点 の流量制約が 」となるグラフを作れば良いです。

頂点流量制約付きのフローの解き方は蟻本などを参照してください。

ソースコード

長いのでフローの部分は省略しています。

Div 2

bool bomb[55];
int dp[55][55];
class ApocalypseEasy {
    public:
    int maximalSurvival(vector<int> p, vector<int> position, int t) {
        memset(bomb, false, sizeof(bomb));
        int N = p.size() + 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                dp[i][j] = (i != j ? INF : 0);
            }
        }

        for(int i=0; i<N-1; i++) {
            int u = i+1, v = p[i];
            dp[u][v] = dp[v][u] = 1;
        }

        for(int k=0; k<N; k++) {
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    chmin(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }

        BipartiteMatching fl(N, N, 0);
        int source = 2 * N, sink = source + 1;
        for(size_t i=0; i<position.size(); i++) {
            bomb[ position[i] ] = true;
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(dp[i][j] <= t) fl.add_edge(i, N+j, 1);
            }
        }

        for(int i=0; i<N; i++) {
            if(bomb[i]) fl.add_edge(source, i, 1);
            else fl.add_edge(N+i, sink, 1);
        }

        return fl.solve();
    }
};

Div 1

bool bomb[55];
bool edge[55][55];
class Apocalypse {
    public:
    int maximalSurvival(vector<int> p, vector<int> position, int t) {
        memset(bomb, false, sizeof(bomb));
        int N = p.size() + 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                edge[i][j] = (i != j ? false : true);
            }
        }

        for(int i=0; i<N-1; i++) {
            int u = i+1, v = p[i];
            edge[u][v] = edge[v][u] = true;
        }

        Flow<int> fl(2*N*(t+1) + 2);
        int source = 2*N*(t+1), sink = source + 1;
        for(size_t i=0; i<position.size(); i++) {
            bomb[ position[i] ] = true;
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(edge[i][j]) {
                    for(int k=0; k<t; k++) {
                        int u = (2*k+1)*N+i, v = (2*k+2)*N+j;
                        fl.add_edge(u, v, 1);
                    }
                }
            }
        }

        for(int i=0; i<N; i++) {
            if(bomb[i]) fl.add_edge(source, i, 1);
            else fl.add_edge((2*t+1)*N+i, sink, 1);
            for(int k=0; k<=t; k++) {
                int u = 2*k*N+i, v = u + N;
                fl.add_edge(u, v, 1);
            }
        }

        return fl.max_flow(source, sink);
    }
};