최소 비용 최대 유량(MCMF)

http://kks227.blog.me/220810623254 에서 가져와서 핵심만 정리했습니다.

어떤 그래프에서 유량을 흘리는데 최대 유량을 흘리고자 합니다. 그런데 최소한의 비용을 들여서

흘리는게 목적입니다. 비용은 간선마다 다르며, 어떤 간선의 비용이 d이고, 유량이 f만큼

흐른다고 하면 비용은 d*f입니다.(d*k라고 나와있는데 오타인 듯..)

예로 위에서 빨간색으로 유량이 흐른다고 할때 비용은 17입니다.

방법론 : 포드 폴커슨, 에드몬드 카프 알고리즘과 비슷한데 매번 찾는 경로가 최단 경로입니다. 

매번 최단 경로를 찾고, 이 경로로 흐를수 있는 최대 유량을 흘려보내면서 경로값*유량을 더해주면

된다네요.(위의 d*f를 말하는듯)

주의점 : 음의 가중치가 있는 그래프에서도 잘 작동해야 함. 역방향 간선의 경우 -로 값을 주고 한다.

음의 가중치가 있는 그래프에서 최단경로를 찾는 알고리즘으로 벨만 포드가 있는데, 이걸 조금 변형시킨

SPFA라는 최단 경로 알고리즘을 주로 사용한다고 함.

https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm

개념이 너무 어려워서 아래 소스코드까지 가지고 왔습니다. 다시 말하지만 출처는 맨 위의 블로그입니다.

https://www.acmicpc.net/problem/11405 를 푼 소스코드 분석. (전체 소스코드는 맨 아래에.)

순서대로 어떻게 흘러가는지 정리했습니다.

변수 선언부.

    // 정점 번호: 0~MAX_N: 서점, MAX_N~MAX_N*2: 사람
    int N, M;
    int c[MAX_V][MAX_V] = {0}; // 각 간선의 용량
    int d[MAX_V][MAX_V] = {0}; // 각 간선의 비용
    int f[MAX_V][MAX_V] = {0}; // 각 간선에 흐르는 중인 유량
    vector<int> adj[MAX_V]; // 각 정점의 인접 리스트

1. N,M을 입력받고 그래프 모델링. 각 사람이 책을 사고 끝으로 간다고 가정.

100은 첫번째사람, 101은 두번째사람, ... 100~201의 비용은 0 

    scanf("%d %d", &N, &M);
    // 각 사람 정점과 싱크 정점 사이 간선 추가 (비용 0)
    for(int i=MAX_N; i<MAX_N+N; i++){
        scanf("%d", &c[i][E]);
        adj[E].push_back(i);
        adj[i].push_back(E);
    }

2. 각 온라인 서점이 가지고 있는 책의 갯수 모델링. 시작점은 200이고 온라인 서점은

0,1,2,~~~이런식으로 증가. 시작점과 각 온라인 서점간의 비용은 0

    // 소스 정점과 각 서점 정점 사이 간선 추가 (비용 0)
    for(int i=0; i<M; i++){
        scanf("%d", &c[S][i]);
        adj[S].push_back(i);
        adj[i].push_back(S);
    }

3. 서점과 사람 사이에 어느 서점이 어느 사람한테 보내려면 얼마의 배송시간이 드는지 간선 이어줌.

아래 그래프는 0번 서점만 이어놓은것. 아래 소스코드에 적혀있듯이 역방향 간선은 -로 이어준다.

    // 서점과 사람 사이 간선 추가 (비용 C_ij)
    for(int i=0; i<M; i++){
        for(int j=MAX_N; j<MAX_N+N; j++){
            scanf("%d", &d[i][j]);
            d[j][i] = -d[i][j]; // 역방향 간선의 비용: 순방향의 -1배
            c[i][j] = INF; // 순방향 간선만 용량이 1 이상
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }

4. MCMF돌려줌.

아래는 위 출처의 총 소스코드. 알고리즘 설명 갑인것 같다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 100; // 최대 N, M
const int MAX_V = 2*(MAX_N+1); // 최대 정점 개수
const int S = MAX_V-2; // 소스 정점 번호
const int E = MAX_V-1; // 싱크 정점 번호
const int INF = 1000000000;
 
int main(){
    // 정점 번호: 0~MAX_N: 서점, MAX_N~MAX_N*2: 사람
    int N, M;
    int c[MAX_V][MAX_V] = {0}; // 각 간선의 용량
    int d[MAX_V][MAX_V] = {0}; // 각 간선의 비용
    int f[MAX_V][MAX_V] = {0}; // 각 간선에 흐르는 중인 유량
    vector<int> adj[MAX_V]; // 각 정점의 인접 리스트
 
    scanf("%d %d", &N, &M);
    // 각 사람 정점과 싱크 정점 사이 간선 추가 (비용 0)
    for(int i=MAX_N; i<MAX_N+N; i++){
        scanf("%d", &c[i][E]);
        adj[E].push_back(i);
        adj[i].push_back(E);
    }
    // 소스 정점과 각 서점 정점 사이 간선 추가 (비용 0)
    for(int i=0; i<M; i++){
        scanf("%d", &c[S][i]);
        adj[S].push_back(i);
        adj[i].push_back(S);
    }
    // 서점과 사람 사이 간선 추가 (비용 C_ij)
    for(int i=0; i<M; i++){
        for(int j=MAX_N; j<MAX_N+N; j++){
            scanf("%d", &d[i][j]);
            d[j][i] = -d[i][j]; // 역방향 간선의 비용: 순방향의 -1배
            c[i][j] = INF; // 순방향 간선만 용량이 1 이상
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }
 
    int result = 0; // 최소 비용
    // MCMF 시작
    while(1){
        int prev[MAX_V], dist[MAX_V];
        bool inQ[MAX_V] = {0}; // 해당 정점이 큐 안에 있는가?
        queue<int> Q;
        fill(prev, prev+MAX_V, -1);
        fill(dist, dist+MAX_V, INF);
        dist[S] = 0;
        inQ[S] = true;
        Q.push(S);
 
        while(!Q.empty()){
            int curr = Q.front();
            Q.pop();
            inQ[curr] = false; // 큐에서 꺼냄
            for(int next: adj[curr]){
                // 최단 경로를 찾는 중이지만, 여전히 여유 용량 있어야 함
                if(c[curr][next]-f[curr][next] > 0 && dist[next] > dist[curr]+d[curr][next]){
                    dist[next] = dist[curr] + d[curr][next];
                    prev[next] = curr;
                    // 큐에 들어있지 않다면 큐에 넣음
                    if(!inQ[next]){
                        Q.push(next);
                        inQ[next] = true;
                    }
                }
            }
        }
        // 더 이상 경로가 없다면 루프 탈출
        if(prev[E] == -1) break;
 
        // 경로상에서 가장 residual이 작은 간선을 찾아 최대 흘릴 수 있는 flow 찾음
        int flow = INF;
        for(int i=E; i!=S; i=prev[i])
            flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
 
        // 경로상의 모든 간선에 flow만큼의 유량을 흘림
        for(int i=E; i!=S; i=prev[i]){
            result += flow * d[prev[i]][i]; // 총 비용이 각 간선 비용만큼 증가
            f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;
        }
    }
    // 정답 출력
    printf("%d\n", result);
}