(라이님 블로그 대회 알고리즘 따라잡기 27) 최소 비용 최대 유량(Minimum Cost Maximum Flow)

MCMF를 푸는 알고리즘을 배웠다.

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220810623254&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

최소 비용 최대 유량(Minimum Cost Maximum Flow) (수정: 2019-08-14)

 

그래프 관련된 알고리즘을 몇 개 보니 이제는 눈에 좀 익는거 같다. 

 

이 알고리즘은 최단 경로(비용이 최소가 되는 거리)를 찾아 유량을 흘려주고, 더 이상의 최단 경로가 없을 때까지 유량을 흘려주는 알고리즘으로 SPFA(Shortest path faster algorithm)이 가장 많이 사용된다.

 

시간복잡도는 O(VEf)이지만 라이님에 따르면 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 capacity[MAX_V][MAX_V] = { 0 }; // 각 간선의 용량
    int cost[MAX_V][MAX_V] = { 0 }; // 각 간선의 비용
    int flow[MAX_V][MAX_V] = { 0 }; // 각 간선에 흐르는 중인 유량
    vector<int> adj[MAX_V]; // 각 정점의 인접 리스트

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

    int totalCost = 0; // 최소 비용
    // MCMF 시작
    while (1) {
        // prev : 각 정점의 이전 정점 저장
        // dist : 소스 정점에서 각 정점까지의 거리 저장(초기값 inf)
        vector<int> prev(MAX_V, -1), dist(MAX_V, INF);
        vector<bool> inQ(MAX_V, false);
        queue<int> Q;

        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 (capacity[curr][next] - flow[curr][next] > 0 && dist[next] > dist[curr] + cost[curr][next]) {
                    dist[next] = dist[curr] + cost[curr][next];
                    prev[next] = curr;
                    // 큐에 들어있지 않다면 큐에 넣음
                    if (!inQ[next]) {
                        Q.push(next);
                        inQ[next] = true;
                    }
                }
            }
        }
        // 더 이상 경로가 없다면 루프 탈출
        if (prev[E] == -1) break;

        // 경로상에서 가장 residual이 작은 간선을 찾아 최대 흘릴 수 있는 flow 찾음
        int new_flow = INF;
        for (int i = E; i != S; i = prev[i])
            new_flow = min(new_flow, capacity[prev[i]][i] - flow[prev[i]][i]);

        // 경로상의 모든 간선에 flow만큼의 유량을 흘림
        for (int i = E; i != S; i = prev[i]) {
            totalCost += new_flow * cost[prev[i]][i]; // 총 비용이 각 간선 비용만큼 증가
            flow[prev[i]][i] += new_flow;
            flow[i][prev[i]] -= new_flow;
        }
    }
    // 정답 출력

    printf("%d\n", totalCost);
}