백준 16126번 - 동아리방 확장

 

16126번: 동아리방 확장

 

풀이:

https://rkm0959.tistory.com/124 처럼 2는 2개의 3과 연결되어야 하고, 3은 1개의 3 또는 1개의 2와 연결되어야 한다는 걸 플로우로 모델링하면 된다.

처음에는 에드몬드-카프를 썼는데 TLE가 나왔고, bipartite matching을 써서 통과했다.

푼 사람 중에서 속도가 가장 느린 축에 속하는데 플로우로 모델링한 점에 만족하고 넘어간다.

 

#include "prelude.h"

constexpr int INF = INT_MAX / 2;
constexpr int xs[4] = {-1, 0, 0, 1};
constexpr int ys[4] = {0, -1, 1, 0};

using namespace std;
using pii = pair<int, int>;
using pli = pair<long, int>;
using ll = long long;

class BipartiteMatching {
public:
    BipartiteMatching(int N, int M) : graph(N), A(N, -1), B(M, -1), cnt(-1) {}

    void addEdge(int from, int to) {
        graph[from].push_back(to);
    }

    bool dfs(vector<bool>& visited, int cur) {
        visited[cur] = true;
        for (auto to : graph[cur]) {
            if (B[to] == -1 || (!visited[B[to]] && dfs(visited, B[to]))) {
                A[cur] = to;
                B[to] = cur;
                return true;
            }
        }
        return false;
    }

    int count() {
        if (cnt != -1) {
            return cnt;
        }
        cnt = 0;
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] == -1) {
                vector<bool> visited(A.size(), false);
                if (dfs(visited, i)) {
                    ++cnt;
                }
            }
        }
        return cnt;
    }

    vector<vector<int>> graph;
    vector<int> A;
    vector<int> B;
    int cnt;
};

int board[101][101];

int main() {
    DEFIN2(N, M);
    bool inval = false;
    FOR(i, N) {
        FOR(j, M) {
            IN(board[i][j]);
            if (board[i][j] < 2) {
                inval = true;
            }
        }
    }
    if (inval) {
        PRINTLN("HOMELESS");
        return 0;
    }

    BipartiteMatching bm(N*M*2+2, N*M*2+2);
    auto to = [&](int x, int y) { return (x * M + y) * 2; };

    int totin = 0;
    int totout = 0;
    FOR(i, N) {
        FOR(j, M) {
            if ((i + j) % 2 == 0) {
                if (board[i][j] == 4) {
                    continue;
                }
                totin += (board[i][j] == 3 ? 1 : 2);
                for (int k = 0; k < 4; ++k) {
                    int ni = i + xs[k];
                    int nj = j + ys[k];
                    if (Board(ni, nj, N, M)) {
                        int f = board[i][j];
                        int t = board[ni][nj];
                        if (f == 2 && t == 3) {
                            bm.addEdge(to(i, j), to(ni, nj));
                            bm.addEdge(to(i, j) + 1, to(ni, nj));
                        } else if (f == 3 && t == 2) {
                            bm.addEdge(to(i, j), to(ni, nj));
                            bm.addEdge(to(i, j), to(ni, nj) + 1);
                        } else if (f == 3 && t == 3) {
                            bm.addEdge(to(i, j), to(ni, nj));
                        }
                    }
                }
            } else {
                if (board[i][j] == 4) {
                    continue;
                }
                totout += (board[i][j] == 3 ? 1 : 2);
            }
        }
    }

    auto maxflow = bm.count();
    if (maxflow == max(totin, totout)) {
        PRINTLN("HAPPY");
    } else {
        PRINTLN("HOMELESS");
    }

    return 0;
}