MCMF(Minimum Cost Maximum Flow) 알고리즘

---

목록

1. MCMF(Minimum Cost Maximum Flow)란?

2. MCMF(Minimum Cost Maximum Flow) 동작 원리

(+주의할 점, 시간 복잡도)

3. MCMF(Minimum Cost Maximum Flow) 소스 코드

4. MCMF(Minimum Cost Maximum Flow) 관련 문제

---

1. MCMF(Minimum Cost Maximum Flow)란?

이전까지는 플로우 문제에서 유량에 대해서만 다루는 문제들을 보았다.

이번에는 그래프의 간선에 유량과 비용이 있다 치자.

예를들어 A->B로 물을 흘려보내는데 물이 시간당 100L가 흐를 수 있는데 시간당 흘리는 비용이 10000원이고

A->C로 물을 흘려보내는데 물이 시간당 10L가 흐를 수 있는데 시간당 흘리는 비용이 100000원이다.

이렇게 유량, 비용이 함께 있는 그래프에 대해 최소 비용으로 최대 유량을 구하는 문제를 MCMF라고 한다.

2. MCMF(Minimum Cost Maximum Flow) 동작 원리

MCMF 말 그대로 최소 비용을 구하여 그 최소 비용에 해당하는 간선으로의 최대 유량을 구하는 문제이다.

즉, 최소 비용이라 함은 최단 거리를 구하는 문제가 되고, 최단 거리를 구하여 최대 유량을 구하면 된다.

이때 최단 거리는 최단 거리 알고리즘을 쓰면 되지만, 이 문제에서 비용이 음수가 될 수 있기에 우리는 다익스트라가 아닌

벨만포드 알고리즘을 써야한다.

이때 벨만포드 알고리즘을 써도 무방하지만, 특정 문제에서 시간 복잡도에 걸릴 수 있으므로 벨만포드 성능을 향상시킨 SPFA 알고리즘을 이용한다. (SPFA 알고리즘 :: http://www.crocus.co.kr/1089?category=209527)

결국 SPFA를 통한 최소 비용을 구하고 그때의 최대 유량을 구하면 되니 결과값은 경로 비용의 합 * 유량을 더해주면 된다.

MCMF에서 조심해야할 점

이전에 최대 유량 문제를 풀 때, 역방향 간선으로 유량을 흘리게 되면 유량이 상쇄되어 순방향으로 흐르던 유량이 사라지는 방식을 이용하여 최대 유량을 구하곤 했다. 3. 유량의 대칭성 :: f(u,v) = -f(u,v) << http://www.crocus.co.kr/741 >>

따라서 역방향 간선으로 유량을 흘리게 될 때 우리는 비용도 역방향으로 줄 수 있어야 한다.

즉, A->B로 비용이 10이라면 B->A로의 비용을 -10으로 주어야 한다.

시간 복잡도는 벨만포드 알고리즘에 의해 O(V*E)가 기본이 되고, MCMF에서는 O(V*E*f)가 된다.

이때 SPFA의 시간 복잡도는 O(V*E)지만 이것보다는 빠르게 동작한다하여 O(E) 혹은 O(V+E)로도 불리기에

O(E*f) 혹은 O((V+E)*f)라고 가정한다면, 여러 문제들을 풀기에 시간복잡도는 충분하다.

3. MCMF(Minimum Cost Maximum Flow) 소스 코드

대표적인 문제 [11408번] 열혈강호 5 :: https://www.acmicpc.net/problem/11408 를 이용하여 소스 코드를 구현해보자.

직원이 N명이고 해야할 일이 M개가 있다. 이때 강호가 지급해야 하는 월급이 있고 직원이 할 수 있는 일의 목록이 있을때 

최소 월급(MC)으로 최대 몇개의 일(MF)을 시킬 수 있는지가 문제이다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
const int MAX_V = 900;
const int S = MAX_V - 2;
const int T = MAX_V - 1;
const int WORK = 400;
const int INF = 987654321;
 
vector<int> adj[MAX_V];
int c[MAX_V][MAX_V];
int f[MAX_V][MAX_V];
int d[MAX_V][MAX_V];
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    // S :: 898   T :: 899   직원 :: 1 ~ 400   일 :: 401 ~ 800
 
    // S와 직원을 연결
    for (int i = 1; i <= n; i++)
    {
        c[S][i] = 1;
 
        adj[S].push_back(i);
        adj[i].push_back(S);
    }
 
    // T와 일을 연결
    for (int i = 1; i <= m; i++)
    {
        c[i + WORK][T] = 1;
 
        adj[i + WORK].push_back(T);
        adj[T].push_back(i + WORK);
    }
 
    // 입력값 처리
    for (int i = 1; i <= n; i++)
    {
        int wNum;
        scanf("%d", &wNum);
 
        for (int j = 0; j < wNum; j++)
        {
            int workNo, cost;
            scanf("%d %d", &workNo, &cost);
 
            adj[i].push_back(workNo + WORK);
            adj[workNo + WORK].push_back(i);
 
            d[i][workNo + WORK] = cost;
            d[workNo + WORK][i] = -cost;
 
            c[i][workNo + WORK] = 1;
        }
    }
 
    int result = 0;
    int cnt = 0;
 
    while (1)
    {
        int prev[MAX_V], dist[MAX_V];
        bool inQ[MAX_V] = { 0 };
 
        // SPFA
        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 here = q.front();
            q.pop();
 
            inQ[here] = false;
 
            for (int i = 0; i < adj[here].size(); i++)
            {
                int next = adj[here][i];
                if (c[here][next] - f[here][next] > 0 && dist[next] > dist[here] + d[here][next])
                {
                    dist[next] = dist[here] + d[here][next];
                    prev[next] = here;
                    if (!inQ[next])
                    {
                        q.push(next);
                        inQ[next] = true;
                    }
                }
 
            }
        }
 
        if (prev[T] == -1)
            break;
 
        // 최대 유량
        int flow = INF;
 
        for (int i = T; i != S; i = prev[i])
            flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
 
        for (int i = T; i != S; i = prev[i])
        {
            result += flow * d[prev[i]][i];
            f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;
        }
 
        cnt++;
    }
 
    printf("%d\n%d\n", cnt, result);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

우선 Source와 직원, 직원과 일, 일과 Sink를 연결해준다.(문제의 요구사항에 맞게)

그 후 S->T로가는 최단 거리(최소 비용)을 SPFA를 이용하여 구해준다.

마지막으로 그 최단 거리(최소 비용)가 존재한다면 유량을 흘러 보내준다.

이 과정을 반복하여 최대 유량을 구할 수 있다.

5. MCMF(Minimum Cost Maximum Flow) 관련 문제

http://www.crocus.co.kr/search/MCMF