백준 17412번: 도시 왕복하기 1 - Network Flow 문제

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

17412번: 도시 왕복하기 1

1.문제설명

 

1번에서 2번으로 갈 수 있는 모든 경로를 구해야 한다.

단 한 경로에 포함된 길이 다른 경로에 포함되면 안된다

 

 

---

 

2.접근방법[알고리즘]

 

문제가 처음 접했을 때 DFS로 노드를 순환하면서 풀 수 있을 것 같지만

 

그럴 수 없다.

 

이 문제는 Network Flow(최대유량) 알고리즘을 알아야 풀 수 있다.

 

한 간선을 한 번씩 방문할 수 있을 때 2번으로 갈 수 있는 경우가 몇 개 인지 구해야한다.

 

한 간선을 한 번씩 방문할 수 있다는 말은

 

한 간선에 1명만 이동할 수 있다는 말과 같고

 

이 때 2번으로 총 몇명이 도착 할 수 있는지 최대유량을 구해야 하는 문제다.

 

 

 

 

 

---

 

 

 

3.문제풀이코드 C++

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

const int MAX = 401;

int n, p,res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
		fill(d, d + MAX, -1);
        queue<int> Q;
        d[start] = 0;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;

        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }
        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }


}

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

    cin >> n >> p;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;

        c[a][b] = 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    maxFlow(1, 2);

    cout << res << '\n';
   

    return 0;
}

백준 17412번