백준 2316번: 도시 왕복하기 2 (C++)

접근

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

2316번: 도시 왕복하기 2

네트워크 플로우에서 에드몬드카프 알고리즘을 이용하여 푸는 문제임은 알았으나 도시에 한번만 방문하게 하기 위한 방법을 찾기 위해 visited 배열 등 갖가지 방법을 다 쓰다가 못풀어 다른 분의 풀이를 참고하게 되었다.

핵심은 한개의 마을을 2개의 정점, in 정점과 out 정점으로 나누고 이 둘을 capacity 1로 주는 것이다. 이렇게 된다면 여러 마을에서 in 정점으로 여러번 방문되어도 마을 내부의 in 정점에서 out 정점으로 가는 유량의 최대값이 1로 정해져있기 때문에 더이상 탐색이 불가능해지게 된다. 이렇게 정점을 2배로 하고 에드몬드카프 알고리즘을 이용하여 최대유량을 탐색한다면 정답을 구할 수 있게 된다.

코드

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 801
#define out 400

int N, P, ans;
int flow[MAX_N][MAX_N];
int cap[MAX_N][MAX_N];
vector<int> grid[MAX_N];

void edmond_karp() {
    while (1) {
        queue<int> Q;
        Q.push(1);
        int parent[MAX_N];
        fill(parent, parent + MAX_N, -1);
        int minflow = 987654321;

        while (!Q.empty()) {
            int cur = Q.front();
            Q.pop();
            for (int next : grid[cur]) {
                if (cap[cur][next] - flow[cur][next] > 0 && parent[next] == -1) {
                    Q.push(next);
                    parent[next] = cur;
                    if (next == 2) break;
                }
            }
        }
        if (parent[2] == -1) break;
        for (int i = 2; i != 401; i = parent[i]) {
            minflow = min(minflow, cap[parent[i]][i] - flow[parent[i]][i]);
        }
        for (int i = 2; i != 401; i = parent[i]) {
            flow[parent[i]][i] += minflow;
            flow[i][parent[i]] -= minflow;
        }
        ans += minflow;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> P;
    // 마을 내부를 in 정점(i) 와 out 정점(i + out) 으로 나누어 두 정점 사이의 cap을 1로 지정한다.
    for (int i = 1; i <= N; i++) {
        grid[i].push_back(i + out);
        grid[i + out].push_back(i);
        cap[i][i + out] = 1;
    }
    // 입력 받은 마을 사이의 관계를 in 정점과 out 정점으로 나누어 서로 연결해준다.
    int from, to;
    for (int i = 0; i < P; i++) {
        cin >> from >> to;
        grid[from + out].push_back(to);
        grid[to].push_back(from + out);
        cap[from + out][to] = 1;
        grid[to + out].push_back(from);
        grid[from].push_back(to + out);
        cap[to + out][from] = 1;
    }
    edmond_karp();
    cout << ans << endl;

    return 0;
}

더 생각해 볼 것?

네트워크 플로우 알고리즘을 이용하는 문제들을 더욱 다양하게 풀어보아야 겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!