Algorithm in A..Z - Network Flow

개념

유량이 있는 그래프에서 얼마나 많은 유량을 보낼 수 있는지 확인하는 알고리즘

 

유량(Flow) : 두 정점 사이에서 흐르는 유량

용량(Capacity) : 두 정점 사이에서 최대로 흐를 수 있는 유량

소스(Source) : 유량이 시작되는 정점

싱크(Sink) : 유량이 도착하는 정점

 

용량 제한 속성 (Flow <= Capacity)

유량이 흐를 수 있는 최대 양은 용량이다.

=> 유량은 용량을 넘을 수 없다.

 

유량의 대칭성

A -> B로 10이 흘렀으면, B -> A로 다시 10을 보낼 수 있다.

=> 유량을 보낼 경로를 찾을 때 보통 BFS를 사용하고 BFS는 우선순위를 고려하지 않고 경로를 찾게 된다. 이럴 때 최대로 흐르는 경로가 아닌 다른 경로를 선택하는 문제를 해결할 때 필요한 개념이다.

---

작동원리

1. 유량 그래프를 모델링한다

=> 역방향 간선도 필수적으로 추가해야한다.

2. BFS를 이용하여 SOURCE에서 SINK로 가는 경로를 찾는다.

=> isVisited와 cap > flow로 갈 수 있는 경로를 확인.

3. 갈 수 있는 경로에서 흐를 수 있는 유량을 찾는다.

=> BFS를 할 때 역추적 할 수 있도록 배열에 저장한다.

=> 흐를 수 있는 경로는 경로중 cap - flow가 가장 작은 값이다.

4. 경로에서 Flow를 업데이트한다.

5. 2 ~ 4번을 경로가 존재하면 반복한다.

---

시간 복잡도

O(VE^2)

---

문제

11495 격자 0 만들기

www.acmicpc.net/problem/11495

11495번: 격자 0 만들기

---

코드

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

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<vector<int>> board(n, vector<int>(m));
        for (auto &ve : board) {
            for (auto &i : ve) {
                cin >> i;
            }
        }

        const int SOURCE = n*m;
        const int SINK = SOURCE + 1;
        vector<vector<int>> graph(SINK + 1), flow(SINK + 1, vector<int>(SINK + 1)), cap(SINK + 1, vector<int>(SINK + 1));
        for (int i = 0;i < n;++i) {
            for (int j = 0;j < m;++j) {
                int index = i * m + j;
                if ((i + j) % 2) {
                    graph[SOURCE].emplace_back(index);
                    graph[index].emplace_back(SOURCE);
                    cap[SOURCE][index] = board[i][j];

                    for (int k = 0;k < 4;++k) {
                        int xx = j + dx[k];
                        int yy = i + dy[k];

                        if (xx < 0 || xx >= m || yy < 0 || yy >= n) {
                            continue;
                        }

                        int next = yy * m + xx;
                        graph[index].emplace_back(next);
                        graph[next].emplace_back(index);
                        cap[index][next] = INT32_MAX;
                    }
                } else {
                    graph[index].emplace_back(SINK);
                    graph[SINK].emplace_back(index);
                    cap[index][SINK] = board[i][j];
                }
            }
        }

        int result = 0;
        while (true) {
            queue<int> que;
            vector<int> pre(SINK + 1, - 1);
            vector<bool> isVisited(SINK + 1, false);

            que.emplace(SOURCE);
            isVisited[SOURCE] = true;
            while (!que.empty()) {
                auto now = que.front(); que.pop();

                for (auto &next : graph[now]) {
                    if (isVisited[next] || cap[now][next] - flow[now][next] <= 0) {
                        continue;
                    }

                    que.emplace(next);
                    isVisited[next] = true;
                    pre[next] = now;
                }
            }

            if (!isVisited[SINK]) {
                break;
            }

            int f = INT32_MAX;
            for (int i = SINK;i != SOURCE;i = pre[i]) {
                f = min(f, cap[pre[i]][i] - flow[pre[i]][i]);
            }

            for (int i = SINK;i != SOURCE;i = pre[i]) {
                flow[pre[i]][i] += f;
                flow[i][pre[i]] -= f;
            }

            result += f;
        }

        for (int i = 0;i < n;++i) {
            for (int j = 0;j < m;++j) {
                int index = i * m + j;
                if ((i + j) % 2) {
                    result += cap[SOURCE][index] - flow[SOURCE][index];
                } else {
                    result += cap[index][SINK] - flow[index][SINK];
                }
            }
        }

        cout << result << "\n";
    }
}