SoundHound Inc. Programming Contest 2018 (春): C - 広告

https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c

問題概要

各マスが '*' もしくは '.' で構成されたr行c列のグリッドが与えられる。'.'のマスに広告を打てるが、広告を打ったマスの上下左右4マスには広告を打つことができなくなる。最大で何マスに広告を打つことができるか求めよ。

r, c <= 40

解法

  1. '.'マスを頂点とし、上下左右で繋がった'.'マス間に辺を張ったグラフを考えると、問われているのは「このグラフの最大安定集合のサイズを求めよ」と同じことである。
  2. グリッドグラフは2部グラフである。
  3. 2部グラフの最大安定集合は最大フローを用いて求めることができる。

2部グラフの最大安定集合の具体的な求め方は↓のdrkenさんのスライドを見ればわかる(ありがとうございます)。

二部グラフの最小点被覆と最大安定集合と最小辺被覆の求め方

感想

知ってればやるだけだが知らなかったのでやれなかったし記事を書いた

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto A = H.iota.map!(_ => readln.chomp).array;

    auto G = new BipartiteGraph(H * W);
    int cnt = 0;

    foreach (r; 0..H) {
        foreach (c; 0..W) {
            if (A[r][c] == '*') {
                cnt += 1;
                continue;
            }
            foreach (k; 0..2) {
                int nr = r + k;
                int nc = c + 1 - k;
                if (nr >= 0 && nr < H && nc >= 0 && nc < W && A[nr][nc] == '.') {
                    G.add_edge(r * W + c, nr * W + nc);
                }
            }
        }
    }

    G.construct;
    writeln(G.maximum_independent_set.length.to!int - cnt);
}

class BipartiteGraph {
    int n;
    int[][] adj;
    bool[] color;

    this (int n) {
        this.n = n;
        adj = new int[][](n);
        color = new bool[](n);
    }

    void add_edge(int u, int v) {
        adj[u] ~= v;
        adj[v] ~= u;
    }

    bool construct() {
        auto used = new bool[](n);

        bool dfs(int u, bool c) {
            if (used[u])
                return color[u] == c;

            used[u] = true;
            color[u] = c;

            if (adj[u].map!(v => used[v] && color[v] == c).any)
                return false;
            if (adj[u].map!(v => !used[v] && !dfs(v, c^1)).any)
                return false;

            return true;
        }

        foreach (u; 0..n)
            if (!used[u] && !dfs(u, 0))
                return false;

        return true;
    }

    int[] minimum_vertex_cover() {
        int s = n;
        int t = n + 1;
        auto ff = new FordFulkerson(n + 2, s, t);
        foreach (i; 0..n) if (color[i] == 0) ff.add_edge(s, i, 1);
        foreach (i; 0..n) if (color[i] == 1) ff.add_edge(i, t, 1);
        foreach (i; 0..n) if (color[i] == 0) foreach (j; adj[i]) ff.add_edge(i, j, 1);
        ff.run;

        auto used = new bool[](n);
        auto G = new int[][](n);
        foreach (i; 0..n) if (color[i] == 1) foreach (j; adj[i])
            if (ff.flow[j][i])
                G[j] ~= i;
            else
                G[i] ~= j;

        void dfs(int u) {
            if (used[u]) return;
            used[u] = true;
            foreach (v; G[u]) dfs(v);
        }

        foreach (i; 0..n) if (!used[i] && color[i] == 0 && ff.flow[s][i]) dfs(i);

        return n.iota.filter!(i => (color[i] == 0 && !used[i]) || (color[i] == 1 && used[i])).array;
    }

    int[] maximum_independent_set() {
        int[] ret;
        int[] mvc = minimum_vertex_cover;

        if (mvc.empty)
            return n.iota.array;

        for (int i = 0, j = 0; i < n; ++i) {
            if (mvc[j] == i) {
                if (j + 1 < mvc.length)
                    ++j;
            } else {
                ret ~= i;
            }
        }

        return ret;
    }
}


class FordFulkerson {
    int N, source, sink;
    int[][] adj;
    int[][] flow;
    bool[] used;

    this(int n, int s, int t) {
        N = n;
        source = s;
        sink = t;
        assert (s >= 0 && s < N && t >= 0 && t < N);
        adj = new int[][](N);
        flow = new int[][](N, N);
        used = new bool[](N);
    }

    void add_edge(int from, int to, int cap) {
        adj[from] ~= to;
        adj[to] ~= from;
        flow[from][to] = cap;
    }

    int dfs(int v, int min_cap) {
        if (v == sink)
            return min_cap;
        if (used[v])
            return 0;
        used[v] = true;
        foreach (to; adj[v]) {
            if (!used[to] && flow[v][to] > 0) {
                auto bottleneck = dfs(to, min(min_cap, flow[v][to]));
                if (bottleneck == 0) continue;
                flow[v][to] -= bottleneck;
                flow[to][v] += bottleneck;
                return bottleneck;
            }
        }
        return 0;
    }

    int run() {
        int ret = 0;
        while (true) {
            foreach (i; 0..N) used[i] = false;
            int f = dfs(source, int.max);
            if (f > 0)
                ret += f;
            else
                return ret;
        }
    }
}