[6086] 최대유량

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

네트워크 플로우에서 최대 유량 문제입니다.

저도 처음 공부하기 때문에 다른 블로그를 참조하면서 공부했습니다.

필요한 변수 선언입니다.

    int n; //input으로 받는 edge 수
    vector<int> adj[MAX_SIZE]; // 인접
    int capacity[MAX_SIZE][MAX_SIZE] = { 0, }; // 용량
    int flow[MAX_SIZE][MAX_SIZE] = { 0, }; // 흐르는 양
    int prev[MAX_SIZE]; // 경로를 저장(현재 정점의 이전 정점이 무엇이었는지)

입력 부분입니다.

//입력
    scanf("%d", &n);
    getchar();
 
    for (int i = 0; i < n; i++) {
        char s, e;
        int c;
 
        scanf("%c %c %d", &s, &e, &c);
        getchar();
 
        s = ctoi(s), e = ctoi(e); //입력 받은 정점을 숫자로 변환
 
        //같은 간선이 여러개 들어오면 용량이 그만큼 늘어나면 됨
        capacity[s][e] += c;
 
        //정,역방향 간선 추가
        adj[s].push_back(e);
        adj[e].push_back(s);
    }

15번째 줄의 += 부분이 잘이해가 안가실 수 있습니다.

capacity배열은 0으로 전부 초기화 되어있습니다.

입력에서 만약 A -> B 로 가는 edge를 여러개로 준다면

A->B로 가는 유량은 edge의 총 용량만큼이기 때문에 +=로 해주는 것입니다.

19번째에서 역방향 간선까지 추가하는 것이 포드 풀커슨 알고리즘의 핵심인 것 같습니다..(잘은 이해안감..ㅠㅠ)

처리부분입니다.

    //process
    int total_flow = 0;
    const int start = ctoi('A'), end = ctoi('Z');
 
    while (1) {
        for (int i = 0; i < MAX_SIZE; i++) prev[i] = -1;
 
        queue<int> q;
        q.push(start);
 
        while (!q.empty())
        {
            int curr = q.front();
            q.pop();
 
            for (int i = 0; i < adj[curr].size(); i++) {
                int next = adj[curr][i];
 
                if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) {
                    q.push(next);
                    prev[next] = curr;
                    if (next == end) break;
                }
            }
        }
 
        if (prev[end] == -1) break; //Z까지 가는 길이 없으면..
 
        //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택    
        int min_flow = INF;
        for (int i = end; i != start; i = prev[i])
            min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]);
 
        //A에서 Z로 가는 경로에 물을 흘림
        //지나간 경로의 반대 경로에는 -값의 물을 흘림
        for (int i = end; i != start; i = prev[i]) {
            flow[prev[i]][i] += min_flow;
            flow[i][prev[i]] -= min_flow;
        }
        
        total_flow += min_flow;
    }

start, end는 시작과 끝점 입니다. 이 문제에서는 'A'와 'Z'가 되겠습니다.

bfs를 통해서 A->Z로 가는 경로를 찾습니다.

경로는 prev배열에 현재 정점 바로 전의 정점을 저장을 해서 경로를 알 수 있습니다.

예를 들어 A->B->C 라면 prev[A] = -1, prev[B] = A, prev[C] = B 입니다.

최종 도착지점은 항상 'Z'이므로 Z부터 역으로 추적하면 A까지 도달할 수 있습니다.

16번째 줄이 굉장히 중요합니다.

for (int i = 0; i < adj[curr].size(); i++) {
    int next = adj[curr][i];
 
    if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) {
        q.push(next);
        prev[next] = curr;
        if (next == end) break;
    }
}

curr(현재 정점)에서 연결되어 있는 부분을 탐색합니다.

curr->next의 edge에 용량이 꽉 차지 않았다면 그리고 아직 방문하지 않았다면

if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1)

next 정점을 q에 넣고 prev[다음 정점] = 현재 정점 을 넣어줍니다.

만약 다음 정점이 'Z'(end)라면 루프를 빠져나옵니다.

        if (prev[end] == -1) break; //Z까지 가는 길이 없으면..
 
        //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택    
        int min_flow = INF;
        for (int i = end; i != start; i = prev[i])
            min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]);
 
        //A에서 Z로 가는 경로에 물을 흘림
        //지나간 경로의 반대 경로에는 -값의 물을 흘림
        for (int i = end; i != start; i = prev[i]) {
            flow[prev[i]][i] += min_flow;
            flow[i][prev[i]] -= min_flow;
        }
        
        total_flow += min_flow;

주석을 달아 놓은 것처럼

1번째 줄은 정점 'Z'(end)의 이전 정점이 -1라는 것은 bfs에서 Z로 도달하지 못했음을 의미합니다.

그렇기 때문에 더이상 경로가 없음을 의미해서 break;합니다.

그게 아니라면 4번째 줄

bfs로 찾은 경로 구간 중에서 가장 용량이 작은 구간을 선택합니다.

유량을 가장 작은 용량으로 맞춰야만 그 경로로 흘릴 수 있기 때문입니다.

만약 이전 bfs에서 유량이 있을 수 있으므로 최소 용량은 capacity[이전 정점][현재 정점] - flow[이전 정점][현재 정점]으로 구해야 합니다.

그리고

10번째 줄에서 A->Z까지의 경로에 위에서 찾은 min_flow(가장 작은 유량)을 더합니다.

여기서 중요한 부분은 12번째 줄입니다. 경로의 반대 방향으로 -유량을 더해줍니다.

위의 input부분에서 역방향 간선까지 함께 만든 이유입니다.

capacity[curr][next] - flow[curr][next] > 0

아까 이 부분에서 0보다 크면 큐에다가 next를 푸시했는데요.

만약 flow[curr][next]가 -유량이라면 +가 되기 때문에 항상 흐를 수 있습니다.

예시를 보면서 이해하도록 하겠습니다.

이 예시는

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220804885235

를 참고 했으며 제가 설명하는 것 보다 훨씬 상세하게 설명해주셨습니다. 저도 이 블로그를 보고 이해했습니다.

지저분해도 .. 이해해주세요!

bfs로

이 경로까지는 찾으셨을텐데요..

이 유량을 다합치면 9가 되죠.

이게 최대일 것 같지만 그렇지 않습니다.

A->E->F->D->B->G->Z의 경로로 1만큼 흘린다면 Z에 최대 10까지 도달할 수 있습니다.

저는 여기서 D->B구간이 이해가 안갔는데..

이 부분이 -유량을 흘린 이유입니다.

B->D구간의 유량은 3이 흐르고 있습니다.

D->B구간은 애초에 경로가 없습니다. 어떻게 흐를까요?

사실.. 진짜로 흐르는 것이 아니라 B->D구간을 상쇄시키는 느낌??적인 느낌입니다.

D->B구간으로 1을 흘려보내면 B->D구간에서 원래 3이 흐르고 있었으니.. 2가 되겠죠!

그리고 그 B->D에서 상쇄시킨 그 1을  B->G 구간으로 보내는 것입니다!!!!!....

느낌만 이해했습니다.. 완전 이해는 아닌..

어떻게 이런거 까지 생각해냈는지는 잘 모르겠네요...ㅠㅠㅠ

제가 참고하라고 올려드린 블로그..

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220804885235

를 참조해주세요!!!!!! 정말 잘 설명해주셨습니다..

아래는 풀 코드입니다.

/*
input)
11
A B 3
A C 3
A D 4
B E 2
C B 10
C E 1
D F 5
E D 1
E F 1
E Z 2
F Z 5
output)
7
*/
 
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
 
#define MAX_SIZE 52
#define INF 0x7fffffff
 
using namespace std;
 
int ctoi(char c) {
    if (c <= 'Z') return c - 'A';
    return c - 'a' + 26;
}
 
int main() {
    int n;
    vector<int> adj[MAX_SIZE]; // 인접
    int capacity[MAX_SIZE][MAX_SIZE] = { 0, }; // 용량
    int flow[MAX_SIZE][MAX_SIZE] = { 0, }; // 흐르는 양
    int prev[MAX_SIZE]; // 경로를 저장(현재 정점의 이전 정점이 무엇이었는지)
 
    //입력
    scanf("%d", &n);
    getchar();
 
    for (int i = 0; i < n; i++) {
        char s, e;
        int c;
 
        scanf("%c %c %d", &s, &e, &c);
        getchar();
 
        s = ctoi(s), e = ctoi(e); //입력 받은 정점을 숫자로 변환
 
        //같은 간선이 여러개 들어오면 용량이 그만큼 늘어나면 됨
        capacity[s][e] += c;
 
        //정,역방향 간선 추가
        adj[s].push_back(e);
        adj[e].push_back(s);
    }
 
    //process
    int total_flow = 0;
    const int start = ctoi('A'), end = ctoi('Z');
 
    while (1) {
        for (int i = 0; i < MAX_SIZE; i++) prev[i] = -1;
 
        queue<int> q;
        q.push(start);
 
        while (!q.empty())
        {
            int curr = q.front();
            q.pop();
 
            if (curr == end) break;
 
            for (int i = 0; i < adj[curr].size(); i++) {
                int next = adj[curr][i];
 
                if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) {
                    q.push(next);
                    prev[next] = curr;
                }
            }
        }
 
        if (prev[end] == -1) break; //Z까지 가는 길이 없으면..
 
        //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택    
        int min_flow = INF;
        for (int i = end; i != start; i = prev[i])
            min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]);
 
        //A에서 Z로 가는 경로에 물을 흘림
        //지나간 경로의 반대 경로에는 -값의 물을 흘림
        for (int i = end; i != start; i = prev[i]) {
            flow[prev[i]][i] += min_flow;
            flow[i][prev[i]] -= min_flow;
        }
        
        total_flow += min_flow;
    }
 
    printf("%d\n", total_flow);
 
    return 0;
}