[C++] 17412번 도시 왕복하기 1 - 최대 유량

도시 왕복하기 2를 풀면서 같이 푼 문제라서 함께 풀이합니다.

 

1. 문제

• 도시 왕복하기 2: N개의 도시가 P개의 양방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 방문한 도시는 두 번 이상 방문할 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라.
• 도시 왕복하기 1: N개의 도시가 P개의 방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 지난 길은 다시 지날 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라.

<입력>

• -1- \(N(3 \leq N \leq 400)\), \(P(1 \leq P \leq 10,000)\)
• P개의 줄에 연결하는 서로 다른 두 도시 번호가 주어진다.

<출력>

• 왔다 갔다 할 수 있는 최대 횟수를 출력하라.

2. 재정의

• 도시 왕복하기 2: 양방향 그래프에서 1과 2를 왔다 갔다 할 수 있는 서로 겹치지 않는 길의 최대 개수를 구하여라
• 도시 왕복하기 1: 단방향 그래프에서 1과 2를 왔다 갔다 할 수 있는 서로 지나는 도시가 겹치지 않는 길의 최대 개수를 구하여라.

3. 해결 방법

• 도시 왕복하기 2만 설명합니다.
• u <-> v의 경우 u'->v, v'->u의 capacity를 1로 설정하고 최대 유량 알고리즘을 적용하면 최대 유량이 길의 개수이다.

4. 실수한 점, 개선할 점

• 무방향 그래프는 편도를 두 번 한걸로 대체할 수 있는데 이때 편도 두 번은 역방향과 충돌을 일으키지 않는다.
• 역방향도 생각해야 되므로 그래프를 완성할 때 역방향도 추가해야 한다.
• N개로 갈 수 있는 길을 모두 생각하지 않고 길을 미리 찾아놓으면 시간을 많이 단축시킬 수 있다.

 

<코드>

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

const int INF = 987654321;
const int MAX_N = 401;

//도시의 개수 N, 길의 개수 P
int N, P;

vector<int> Edge[MAX_N];
//용량과 유량
int capacity[MAX_N][MAX_N], flow[MAX_N][MAX_N];
//최대 유량
int total_flow;
//부모
int parent[MAX_N];

void input()
{
    cin >> N >> P;
    for(int i=0; i<P; i++) {
        int u, v;
        
        cin >> u >> v;
        
        capacity[u][v] = 1;
        Edge[u].push_back(v);
        Edge[v].push_back(u);
    }
}

//최대 유량 알고리즘
void MaximumFlow() {
    while(1) {
        //BFS
        memset(parent, -1, sizeof parent);
        queue<int> q;
        q.push(1);
        
        //최단으로 2에 도달하는 경로 찾기
        while(!q.empty() && parent[2]==-1) {
            int here = q.front();
            q.pop();
            
            for(auto next : Edge[here])
                if(capacity[here][next] - flow[here][next] > 0 && parent[next] == -1) {
                    q.push(next);
                    parent[next] = here;
                }
        }
        
        //2까지의 경로를 못 찾았다면 더 이상 증가 경로는 없다.
        if(parent[2] == -1)
            break;
        
        int amount = INF;
        for(int p = 2; p!=1; p = parent[p])
            amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
        
        for(int p = 2; p!=1; p = parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        
        total_flow += amount;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    //최대 유량 알고리즘
    MaximumFlow();
    
    cout << total_flow;
    
    return 0;
}

 

<최대 유량 알고리즘 1>

https://everenew.tistory.com/177

[네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘

 

<최대 유량 알고리즘 2>

https://unorderedmap.tistory.com/6

최대 유량 문제(Maximum Flow) - 에드몬드-카프 알고리즘 (Edmonds-Karp Algorithm)

 

<최대 유량 알고리즘 3>

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kks227&logNo=220804885235 

네트워크 유량(Network Flow) (수정: 2019-08-14)

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.