MCMF (Minimum Cost Maximum Flow)

간선마다 유량과 cost가 있는 그래프에서 최대 유량을 구하고, 이 때의 cost를 최소화하는 문제이다. $O(VEf)$로 동작하지만($f$는 최대 유량), SPFA를 사용하면 사실상 $O(Ef)$ 혹은 그보다 빠르게 동작한다. 일반적으로는 문제 모델링에 성공했다면 시간복잡도는 고민하지 않아도 된다.

 

아이디어는 단순하다. Max flow 문제에서와 마찬가지로 source에서 sink까지의 경로를 찾고, 그 경로를 따라 flow를 흘려주는 과정을 반복하면 된다. 다만 여기서는 minimum cost인 경로(최단 경로)를 찾을 것이다. 유량을 흘린 후에도 나중에 그 유량을 제거해야할 수 있는데, 이를 위해서 유량을 흘릴 때마다 역방향 간선을 만들 것이다. 이 역방향 간선의 cost는 기존 cost와 반대여야 한다. 그렇기 때문에 음수 간선을 처리할 수 있는 최단경로 알고리즘(SPFA)을 사용해야 하는 것이다. 처음 모델링에서 음수 사이클이 존재하지 않았다면 계산 과정에서도 음수 사이클이 생기지 않는다고 한다. (참고)

 

아래는 코드이다. (백준 열혈강호5 문제)

#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back

const int MAXN = 410;
const int INF = 1 << 30;

struct EDGE {
	int v, c, d, r;		// vertex, capacity, distance, reverse
	EDGE(int v, int c, int d, int r) : v(v), c(c), d(d), r(r) {}
};

vector<EDGE> ed[MAXN];
int S, E;
int dis[MAXN], pe[MAXN];	// distance(SPFA), previous edge(이전 정점을 가리키는 간선의 index)
bool inq[MAXN];

void addedge(int a, int b, int c, int d) {
	ed[a].eb(b, c, d, ed[b].size());
	ed[b].eb(a, 0, -d, ed[a].size() - 1);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	// TODO : make graph

	int cost = 0, flow = 0;
	while(1) {
		queue<int> q;		// SPFA
		for(int i = 1; i <= E; i++) {
			dis[i] = INF;
			inq[i] = false;
		}
		dis[S] = 0;
		q.push(S);
		inq[S] = true;
		while(!q.empty()) {
			int t = q.front();
			q.pop();
			inq[t] = false;
			for(auto e : ed[t]) if(e.c && dis[t] + e.d < dis[e.v]) {
				dis[e.v] = dis[t] + e.d;
				pe[e.v] = e.r;
				if(!inq[e.v]) {
					q.push(e.v);
					inq[e.v] = true;
				}
			}
		}
		if(dis[E] == INF) break;	// 더 이상 경로 없음
		int f = INF;
		for(int x = E; x != S; x = ed[x][pe[x]].v) {	// 찾은 경로로 흘릴 수 있는 유량 계산
			EDGE &e = ed[x][pe[x]];
			f = min(f, ed[e.v][e.r].c);
		}
		flow += f;
		cost += dis[E] * f;
		for(int x = E; x != S; x = ed[x][pe[x]].v) {	// 간선 뒤집어주기
			EDGE &e = ed[x][pe[x]];
			e.c += f;
			ed[e.v][e.r].c -= f;
		}
	}
	cout << flow << "\n" << cost << "\n";
	return 0;
}

 

 

아래 링크를 통해 공부하였다.

https://m.blog.naver.com/kks227/220810623254

https://www.crocus.co.kr/1090

https://koosaga.com/18