책 구매하기2 - 최대유량(에드몬드-카프 알고리즘)

 

최대 유량은 용량이 정해진 간선들이 있는 그래프에서 출발점->도착점으로 보낼 수 있는 최대 유량을 구하는 문제이다.

최대 유량 문제를 해결하는 아이디어는 포드-풀커슨 방법이다.

포드-풀커슨 알고리즘이라고 부르기도 하는데, 아이디어의 핵심은 음의 유량을 설정하는 것이다.

우선 사이에 간선이 있는 두 정점에 간선이 한 방향으로만 있다면, 반대 방향 간선도 만들어주고, 용량을 0으로 설정한다.

출발점에서 도착점까지의 경로를 dfs로 하나 찾으면, 그 경로에 흘려보낼 유량은 지나치는 모든 간선의 (용량-현재유량)의 min값이

될 것이다.

그렇게 계산한 유량을 흘려보내주고, 지나치는 모든 간선의 반대 방향 간선에 음의 유량을 흘려준다.

처음에는 음의 유량을 설정하는 것이 어떤 의미인지 이해하기 어렵긴 한데, 여러 그래프의 예시를 보다 보면 이해할 수 있다.

우리가 찾은 경로가 최적의 경로가 아닐 수도 있는데 이런 경우에, 다른 경로로 우회를 해야 해서 음의 유량을 보내는 것이 우회 경로를 찾는 것과 같은 역할을 한다.

최대 유량 문제를 설명할 때 자주 나오는 그래프이다.

1번 정점에서 4번 정점으로 유량을 보낼 때, dfs로 찾은 경로가 1->2->3->4라고 하면, min(99,1,99)=1이기 때문에

1의 유량을 보낼 수 있다.

그런데 이렇게 유량을 보내버리면 1->2->4와 1->3->4는 각각 98씩의 유량만 보낼 수 있다.

1->2와 3->4에 이미 1의 유량이 존재하기 때문이다.

그러면 총 유량은 1+98+98이다.

하지만 최대 유량은 직관적으로 알다시피 1->2->4 99와 1->3->4 99로 99+99이다.

이렇게 우리가 찾은 경로가 최적이 아닐 수 있기 때문에 경로를 우회해야 한다.

그런데 여기서 음의 유량을 보내게 되면 어떻게 되는지 보자.

1->2->3->4에 1의 유량을 보내고, 4->3->2->1로 -1의 유량을 보내자.

앞에서 설명했듯이, 반대 방향 간선의 용량은 0이다.

그러면 dfs로 경로를 찾을 때 3->2로 1의 유량을 보낼 수 있다.(용량이 0인데 흐르고 있는 유량이 -1이기 때문이다.)

그렇게 되면, 1->3->2->4의 경로에도 1의 유량을 보낼 수 있다.

그러면 결과적으로 1->2->4로 1이 흐르고, 1->3->4로 1이 흐르는 것과 같은 상황이 된다.

그래서 음의 유량을 보내는 것이 우회 경로를 찾는 것과 같은 효과를 가져오게 된다.

 

처음 볼 때는 이해하기 조금 어렵지만 이해만 한다면 상당히 신기한 알고리즘이다.

지금까지 공부한 알고리즘 중에는 가장 아이디어가 참신했던 것 같다.

그런데 이 포드-풀커슨 방법에는 단점이 있다.

앞에서 했던 것처럼 유량을 보내면, 1->2->3->4로 1을 보내고, 1->3->2->4로 1을 보내는 작업을 99번 해야 한다.

만약 용량이 1억을 넘어가면 시간 초과가 날 수 밖에 없다.

 

이를 해결하기 위해 나온 알고리즘이 에드몬드-카프 알고리즘이다.

크게 다른건 아니고 그냥 dfs로 경로를 찾는 것이 아니라 bfs로 경로를 찾아나간다.

이렇게 하면 99번 반복할 필요 없이 한번에 유량을 보낼 수 있다.

요약하자면

1. 단방향 간선인 경우에 반대 방향 간선도 만들어서 용량을 0으로 설정해준다.

2. bfs로 경로를 찾고, 해당 경로에 보낼 수 있는 유량을 계산해 보낸다.

3. 해당 경로에서 반대 방향 간선에 음의 유량을 보낸다.

4. 증가 경로가 없을 때까지 이 작업을 반복한다.

이렇게 최대 유량 문제를 해결할 수 있다.

 

그래서 이 책 구매하기2 문제를 해결해보자면, 우선 이 문제는 사람마다 구매 가능한 최대 개수가 있고, 서점에서 팔 수 있는 최대 개수가 있다. 이 때 모든 사람과 서점 사이에 책 구매를 진행했을 때 최대 몇권을 살 수 있는 구하는 문제이다.

최대 유량 문제로 바꾸기 위해 그래프를 만들어 줘야 한다.

사람 N명을 정점 1~N으로 설정하고, 서점 M개를 정점 N+1~N+M으로 설정한다.

그리고 0번 정점에서 출발해 N+M+1번 정점으로 유량을 보낸다고 하자.

그러면 0번 정점과 1~N번 정점을 이었을 때 간선의 용량은 i번 사람이 구매 가능한 책의 최대 개수이다.

이렇게 설정하면 유량을 보낼 때 해당 사람은 최대 개수를 넘어서 살 수 없게 된다.

그리고 1~N번 정점과 N+1~N+M 정점은 사람과 서점을 잇는 간선이기 때문에 i번 사람이 j번 서점에서 살 수 있는 책 C(ij)로

용량을 설정해주면 된다.

마지막으로 N+1~N+M 정점과 N+M+1번 정점을 잇는 간선을 만들고 용량을 각 서점이 판매할 수 있는 책의 개수로 설정하면

그래프 설계가 끝난다.

 

이렇게 만들어진 그래프에서 0->N+M+1의 최대 유량을 구하면 되는 문제이다.

//generate graph & set C from A and B
for(int i=1;i<=N;i++)
{
    for(int j=N+1;j<=N+M;j++)
    {
        graph[i].push_back(j);
        graph[j].push_back(i);
    }
}
for(int i=1;i<=N;i++)
{
    graph[i].push_back(0);
    graph[0].push_back(i);
    C[0][i]=A[i];
}
for(int i=N+1;i<=N+M;i++)
{
    graph[i].push_back(N+M+1);
    graph[N+M+1].push_back(i);
    C[i][N+M+1]=B[i-N];
}

그래프를 설정하는 부분이다.

 

int bfs()
{
    int total = 0;
    // loop until no increasing path
    while(1)
    {
        for(int i=0;i<=N+M+1;i++) pre[i]=-1;
        queue<int>Q;
        Q.push(0);
        // find one increasing path
        while(!Q.empty())
        {
            int cur = Q.front();
            Q.pop();
            for(int i=0;i<graph[cur].size();i++)
            {
                int next = graph[cur][i];
                if(C[cur][next]>F[cur][next] && pre[next]==-1)
                {
                    pre[next] = cur;
                    Q.push(next);
                    if(next==N+M+1) break;
                }
            }
        }
        if(pre[N+M+1]==-1) break;
        int flow = 1000000000;
        // find minimum flow in edges
        for(int i=N+M+1;i!=0;i=pre[i])
        {
            flow = min(flow, C[pre[i]][i]-F[pre[i]][i]);
        }
        // set F in forward and reverse
        for(int i=N+M+1;i!=0;i=pre[i])
        {
            F[pre[i]][i] += flow;
            F[i][pre[i]] -= flow;
        }
        total += flow;
    }
    return total;
}

에드몬드-카프 알고리즘 구현 부분이다.

C는 용량, F는 현재 흐르고 있는 유량을 나타낸다.

 

#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int N,M;
int A[104],B[104];
int C[204][204],F[204][204];
int pre[204];
vector<int>graph[204];
int bfs()
{
    int total = 0;
    // loop until no increasing path
    while(1)
    {
        for(int i=0;i<=N+M+1;i++) pre[i]=-1;
        queue<int>Q;
        Q.push(0);
        // find one increasing path
        while(!Q.empty())
        {
            int cur = Q.front();
            Q.pop();
            for(int i=0;i<graph[cur].size();i++)
            {
                int next = graph[cur][i];
                if(C[cur][next]>F[cur][next] && pre[next]==-1)
                {
                    pre[next] = cur;
                    Q.push(next);
                    if(next==N+M+1) break;
                }
            }
        }
        if(pre[N+M+1]==-1) break;
        int flow = 1000000000;
        // find minimum flow in edges
        for(int i=N+M+1;i!=0;i=pre[i])
        {
            flow = min(flow, C[pre[i]][i]-F[pre[i]][i]);
        }
        // set F in forward and reverse
        for(int i=N+M+1;i!=0;i=pre[i])
        {
            F[pre[i]][i] += flow;
            F[i][pre[i]] -= flow;
        }
        total += flow;
    }
    return total;
}
int main()
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&A[i]);
    }
    for(int i=1;i<=M;i++)
    {
        scanf("%d",&B[i]);
    }
    for(int i=1;i<=M;i++)
    {
        for(int j=1;j<=N;j++)
        {
            scanf("%d",&C[j][i+N]);
        }
    }

    //generate graph & set C from A and B
    for(int i=1;i<=N;i++)
    {
        for(int j=N+1;j<=N+M;j++)
        {
            graph[i].push_back(j);
            graph[j].push_back(i);
        }
    }
    for(int i=1;i<=N;i++)
    {
        graph[i].push_back(0);
        graph[0].push_back(i);
        C[0][i]=A[i];
    }
    for(int i=N+1;i<=N+M;i++)
    {
        graph[i].push_back(N+M+1);
        graph[N+M+1].push_back(i);
        C[i][N+M+1]=B[i-N];
    }
    // solve
    int ans = bfs();
    printf("%d",ans);
}

전체 코드이다.