SRM 594 div1 med:FoxAndGo3

最小カットの練習がしたくなったので。

問題:TopCoder Statistics - Problem Statement

解法:最小カットを使って「燃やす埋める問題」を解くの40ページあたりから。

// max_flow
const int MAX_V = 3000;
const int INF = 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};

class FoxAndGo3 {
public:
    int maxEmptyCells(vector <string> board) {
        FordFulkerson *ff = new FordFulkerson();
        int n = board.size();
        int s = n*n+1, t = s+1;
        int empty = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'x') continue;
                empty++;
                if (board[i][j] == '.') {
                    ff->add_edge(s, i*n+j, 0);
                    ff->add_edge(i*n+j, t, 1);
                }
                if (board[i][j] == 'o') {
                    ff->add_edge(s, i*n+j, 1);
                    ff->add_edge(i*n+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 >= n) continue;
                        if (board[ny][nx] == '.') {
                            ff->add_edge(i*n+j, ny*n+nx, INF);
                        }
                    }
                }
            }
        }
        return (empty - ff->max_flow(s, t));
    }
};