[C++] 컨닝 (백준 1014번) - 최대 유량 (Max Flow, Min Cut)

https://www.acmicpc.net/problem/1014

 

빨간 칸에 사람이 앉은 상황에서 파란 칸에는 사람이 앉으면 컨닝이 발생한다.

 

source에서 빨간 칸으로 1로 연결해주고, 빨간 칸에서 그 주변의 앉을 수 있는 파란 칸들로 1로 연결해주고, 각 파란 칸들에서 sink로 1로 연결해주면 그래프를 만들 수 있다.

이 그래프에서 유량이 안 흐르도록 하면 컨닝을 아무도 할 수 없는 상황이 된다. 즉, 유량이 흐르지 않게 하기 위해 끊어야 하는 간선의 최소 비용 합을 구하면 된다. 그걸 min cut이라고 부르고 min cut의 값은 max flow 값과 같다. (max flow는 그래프에서 흐르는 최대 유량을 말한다.)

앉을 수 있는 자리('.'인 자리)의 총 개수에서 min cut 값을 빼면 이 문제의 정답이 된다.

 

각 격자 칸을 하나의 unique한 값으로 변환해주는 conv 함수를 만들어 주었다.

그리고 홀수 칸이면 source(198)에서 연결, 주변의 앉을 수 있는 칸들로 연결해준다.

짝수 칸이면 sink(199)로 연결해준다.

 

// Reference: green55 teamnote
// https://github.com/green5555/Teamnote/blob/master/TeamNote/Ed-Karp.cpp

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

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

const int MAX = 200, INF = INT_MAX;
struct maxflow {
    struct edge {
        int next, cap, flow = 0, rev_idx;
        edge() {}
        edge(int n, int c) : next(n), cap(c) {}
        int remain() {
            return cap - flow;
        }
    };
    vector<edge> adj[MAX];
    void makeEdge(int u, int v, int c) {
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, 0);
        adj[u].back().rev_idx = adj[v].size() - 1;
        adj[v].back().rev_idx = adj[u].size() - 1;
    }
    int parent[MAX];
    pii path[MAX];
    int solve(int S, int E) {
        int ans = 0;
        queue<int> q;
        while (1) {
            memset(parent, -1, sizeof(parent));
            q.push(S);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int i = 0; i < adj[u].size(); ++i) {
                    auto &e = adj[u][i];
                    if (e.remain() > 0 && parent[e.next] == -1) {
                        parent[e.next] = u;
                        path[e.next] = { u, i };
                        q.emplace(e.next);
                    }
                }
            }
            if (parent[E] == -1) break;
            int ret = INF;
            for (int i = E; i != S; i = parent[i])
                ret = min(ret, adj[path[i].first][path[i].second].remain());
            for (int i = E; i != S; i = parent[i]) {
                auto &e = adj[path[i].first][path[i].second];
                e.flow += ret;
                adj[e.next][e.rev_idx].flow -= ret;
            }
            ans += ret;
        }
        return ans;
    }
};

int conv(int i, int j) {return (11 * i + j);}

void solve() {
    maxflow mf;

    int n, m;
    cin >> n >> m;
    vector<vector<bool>> a(n, vector<bool>(m, false));

    int ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            a[i][j] = (c == '.');
            if (a[i][j]) ans++;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!a[i][j]) continue;
            if (j % 2 == 0) {
                mf.makeEdge(conv(i, j), 199, 1);
                continue;
            }
            mf.makeEdge(198, conv(i, j), 1);
            for (int k = 0; k < 6; k++) {
                int nxti = i + dx[k];
                int nxtj = j + dy[k];
                if (nxti < 0 || nxti >= n || nxtj < 0 || nxtj >= m || !a[nxti][nxtj]) continue;
                mf.makeEdge(conv(i, j), conv(nxti, nxtj), 1);
            }
        }
    }

    cout << ans - mf.solve(198, 199) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)