[백준] 6086번 최대 유량 문제 풀이(c++)

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

 

문제

농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다.

두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다.

  +---5---+---3---+    ->    +---3---+

게다가, 병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다.

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

마지막으로, 어떤 것에도 연결돼 있지 않은 파이프는 물을 흐르게 하지 못하므로 제거된다.

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

이로 인해 복잡하게 연결된 모든 배수관들은 한개의 최대 유량을 갖는 배수관으로 만들어진다.

주어진 파이프들의 맵으로부터 우물(A)와 외양간(Z) 사이의 유량을 결정하라.

각 노드의 이름은 알파벳으로 지어져 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

파이프 BC와 CD는 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

그러면 BD와 DZ 역시 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

병렬 연결된 BZ 역시 합쳐진다.

                 B
        A+---3---+---9---+Z

그러면 AB와 BZ 역시 합쳐질 수 있고 용량 3인 배수관 하나가 만들어진다.

        A+---3---+Z

한 파이프들의 집합을 읽고. 두개의 끝점을 가진 파이프로 만들어놓은 뒤 A부터 Z까지 흐르는 최대 유량을 계산하라. 모든 파이프들은 위의 규칙을 적용시켜 줄일 수 있다.

i번째 파이프는 두개의 다른 노드 ai와 bi와 연결돼 있고 Fi (1 ≤ Fi ≤ 1,000)만큼의 유량을 갖는다. 알파벳은 같지만, 대소문자가 다르면 다른 문자이다. 파이프는 양방향으로 흐를 수 있다.

 

아이디어

문제 단순화 :

• 한 파이프들의 집합을 읽고, 두 개의 끝점을 가진 파이프로 만들어 놓은 뒤 A부터 Z까지 흐르는 최대 유량을 계산하라.

• A B 3이 입력되면 노드 A와 노드 B 사이 간선의 용량이 3이라는 뜻이다.

 

-> 따라서 최대 유량 알고리즘(포드 - 풀커슨 알고리즘)을 이용하여 풀 수 있는 가장 간단한 버전의 문제다.

 

자세한 설명은 코드의 주석을 통해 확인할 수 있습니다.

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
#define MAX 52
#define INF 100000000
using namespace std;

int result;//최대 유량;
int c[MAX][MAX]/*capacity용량 */, f[MAX][MAX]/*flow 현재 흐르고 있는 유량*/, d[MAX];//현재 특정한 노드를 방문했는지 확인
vector<int> connect[MAX];//연결된 모든 간선을 표현

int maxFlow(int start, int end)
{
    while (1)
    {
        fill(d, d+MAX,-1); //모든 정점은 방문하지 않은 상태인 -1
        queue<int>q;
        q.push(start); //시작점을 q에 넣는다.
        while(!q.empty()) //bfs
        {
            int x=q.front();
            q.pop(); //q에서 한 개를 꺼낸 후
            for(int i=0;i<connect[x].size();i++)// 해당 노드의 인접 노드를 전부 확인
            {
                int y=connect[x][i];//인접 노드 가져오기
                //방문하지 않은 노드 중에 용량이 남은 경우
                if(c[x][y]-f[x][y]>0 && d[y]== -1)
                {
                    q.push(y);
                    d[y]=x;//해당 인접 노드를 방문했다고 처리. 그 경로를 기억하기 위해 현재 방문한 그 노드에서 그 인접노드로 가는 값으로 넣어준다.
                    if(y==end) break;// 도착지에 도달한 경우
                }
            }
        }
        if(d[end]== -1) break; //모든 경로를 찾은 뒤 탈출
        int flow=INF; // 가능한 경로에서 가장 작은 가능한 유량만큼 흘러줘야 하기 때문에
        for(int i=end;i!=start;i=d[i]) //거꾸로 자기 이전의 노드로 돌아가면서 최소 유량 탐색
        {
            flow=min(flow,c[d[i]][i]-f[d[i]][i]);//자기 자신의 이전 값의 용량에서 자기 자신의 이전 값의 유량을 빼준 것과 flow 의 최솟값을 flow에 넣기
        }
        //최소 유량만큼 추가
        for(int i=end;i!=start;i=d[i])//가능한 유량만큼 flow 더해주기
        {
            f[d[i]][i]+=flow;
            f[i][d[i]]-=flow;//음의 유량도 처리해주기
        }
        result+=flow;
    }
    return result;
}
int func(char c)
{
    int res;
    if(c>=97)
    {
        res=c-97;
        res+=26;
    }
    else
    {
        res=c-65;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N; cin>>N;
    for(int i=0;i<N;i++)
    {
        char a,b; int w; cin>>a>>b>>w;
        int A=func(a); int B=func(b);
        connect[A].push_back(B);
        connect[B].push_back(A);
        c[A][B]+=w;
        c[B][A]+=w;

    }
    cout << maxFlow(0,25) << "\n";
    return 0;
}

코드는 (https://blog.naver.com/ndb796/221237111220)이곳에서 공부하였습니다.

 

- 포드-풀커슨 알고리즘에 대해 알고 싶다면? https://nomadsjh.tistory.com/74

[알고리즘] 최대 유량/포드-풀커슨 알고리즘에 대하여