[BOJ 8551 // C++] Blokada

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 8551번 문제인 Blokada이다.
문제는 아래 링크를 확인하자.

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

 

최소한 몇 개의 방향간선을 지워야 1번 정점에서 \(N\)번 정점으로의 연결된 경로가 없게 할 수 있는지를 묻는 문제이다.

 

이 값은 Max-Flow Min-Cut Theorem에 의해 각 간선의 가중치를 1으로 가정할 때의 1번 정점에서 \(N\)번 정점까지 흘릴 수 있는 최대 유량과 같다.

 

Dinic's Algorithm을 이용해 최대 유량을 구하고 문제를 해결하자. 모든 간선의 가중치가 1인 유량 그래프에서 Dinic's Algorithm의 시간복잡도는 \(O(\min(E\sqrt{E}, E\sqrt{V^{\frac{2}{3}}}))\)이므로 주어지는 입력의 크기가 상식적이라면 문제를 충분히 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
using namespace std;

int ans, src, snk, N, M;
vector<int> G[10002];
bitset<10002> flow[10002];
int lv[10002], trn[10002];
queue<int> que;

bool dfs(int cur) {
    if (cur == snk) return 1;
    int sz = G[cur].size();
    for (int &i = trn[cur]; i < sz; i++) {
        int nxt = G[cur][i];
        if (lv[nxt] != lv[cur] + 1 || !flow[cur][nxt]) continue;
        if (dfs(nxt)) {
            flow[cur][nxt] = 0;
            flow[nxt][cur] = 1;
            return 1;
        }
    }
    return 0;
}

bool bfs() {
    memset(lv, 0, sizeof(lv));
    lv[src] = 1;
    que.push(src);
    while (!que.empty()) {
        int cur = que.front(); que.pop();
        for (auto &nxt:G[cur]) {
            if (lv[nxt] || !flow[cur][nxt]) continue;
            lv[nxt] = lv[cur] + 1;
            que.push(nxt);
        }
    }
    return lv[snk];
}

void dinic() {
    while (bfs()) {
        memset(trn, 0, sizeof(trn));
        while (dfs(src)) ans++;
    }
}

void addedge(int x, int y) {
    flow[x][y] = 1;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
}

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

    cin >> N >> M;
    src = 1, snk = N;
    while (M--) {
        int x, y; cin >> x >> y;
        addedge(x, y);
    }
    dinic();
    cout << ans;
}