백준 17412번: 도시 왕복하기 1 (C++)

접근

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

17412번: 도시 왕복하기 1

네트워크 플로우의 에드몬드카프 알고리즘에서 flow의 최대치를 1로 두었을 때의 결과를 표시하면 되는 문제였다.

네트워크 플로우에 대한 자세한 설명은 아래 글을 참조하였다.

https://yjg-lab.tistory.com/198

[알고리즘] 네트워크 플로우 (Network Flow) - 에드몬드 카프 알고리즘 (Edmonds-Karp)

코드

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

using namespace std;

#define endl '\n'
#define MAX_N 401

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

void edmonds_karp() {
    while (1) {
        queue<int> Q;
        Q.push(1);
        vector<int> parent(N + 1, -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 != 1; i = parent[i]) {
            minflow = min(minflow, cap[parent[i]][i] - flow[parent[i]][i]);
        }
        for (int i = 2; i != 1; 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;
    int a, b;
    for (int i = 0; i < P; i++) {
        cin >> a >> b;
        grid[a].push_back(b);
        grid[b].push_back(a);
        cap[a][b] = 1;
    }

    edmonds_karp();

    cout << ans << endl;

    return 0;
}

더 생각해 볼 것?

...

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