Google Code Jam 2008 World Finals E:The Year of Code Jam

最小カットの練習その2。

問題:Dashboard - World Finals 2008 - Google Code Jam

解法:最小カットを使って「燃やす埋める問題」を解くの54ページあたりから。引っかかったので一応実装について注意すると,'?'と'?'を結ぶ辺は1回しか結んではいけない。
一応ソースコードにコメントつけておくので参考に。
以下ソースコード

// max_flow
const int MAX_V = 3000;
const int INF = 1e9;
const int BIG = 1e6;
class FordFulkerson {
public:
    struct edge {
        int to;
        int cap;
        int rev;
        edge() {}
        edge(int t, int c, int r) : to(t), cap(c), rev(r) {}
    };
    vector<edge> G[MAX_V];
    void add_edge(int from, int to, int cap) {
        G[from].push_back(edge(to, cap, G[to].size()));
        G[to].push_back(edge(from, 0, G[from].size() - 1));
    }
    int max_flow(int s, int t) {
        int flow = 0;
        while (1) {
            for (int i = 0; i < MAX_V; i++) used[i] = false;
            int f = dfs(s, t, INF);
            if (f == 0) return flow;
            flow += f;
        }
    }
private:
    int dfs(int v, int t, int f) {
        if (v == t) return f;
        used[v] = true;
        for (int i = 0; i < G[v].size(); i++) {
            edge &e = G[v][i];
            if (!used[e.to] && e.cap > 0) {
                int d = dfs(e.to, t, min(e.cap, f));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    bool used[MAX_V];
};

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int solve(int n, int m, vector<string> board) {
    FordFulkerson *ff = new FordFulkerson();
    int s = n*m+1, t = s+1;
    int firstScore = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == '#') {
                firstScore += 4;
                for (int k = 0; k < 4; k++) {
                    int ny = i+dy[k];
                    int nx = j+dx[k];
                    if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                    if (board[ny][nx] == '#') firstScore--;
                }
                int tmp = (i+j) % 2;
                if (tmp == 0) {
                    ff->add_edge(s, i*m+j, BIG);
                } else {
                    ff->add_edge(i*m+j, t, BIG);
                }
            }
            if (board[i][j] == '?') {
                firstScore += 4;
                int tmp = (i+j) % 2;
                if (tmp == 0) {
                    ff->add_edge(s, i*m+j, 4);
                    ff->add_edge(i*m+j, t, 0);
                    for (int k = 0; k < 4; k++) {
                        int ny = i+dy[k];
                        int nx = j+dx[k];
                        if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                        // こっちでは'#'と'?'どちらも辺を貼る
                        if (board[ny][nx] != '.') {
                            ff->add_edge(i*m+j, ny*m+nx, 2);
                        }
                    }
                } else {
                    ff->add_edge(s, i*m+j, 0);
                    ff->add_edge(i*m+j, t, 4);
                    for (int k = 0; k < 4; k++) {
                        int ny = i+dy[k];
                        int nx = j+dx[k];
                        if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                        // こっちでは'#'しか辺を貼らない!!
                        if (board[ny][nx] == '#') {
                            ff->add_edge(ny*m+nx, i*m+j, 2);
                        }
                    }
                }
            }
        }
    }
    int p = ff->max_flow(s, t);
    delete ff;
    return firstScore-p;
}

int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        int M, N;
        cin >> N >> M;
        vector<string> board(N);
        for (int j = 0; j < N; j++) {
            string s;
            cin >> s;
            board[j] = s;
        }
        printf("Case #%d: %d\n", i, solve(N, M, board));
    }
    return 0;
}