MCMF (Minimum Cost Maximum Flow)
최소 비용 최대 유량 문제 = 최소 비용을 들여서, 최대 유량을 흘린다
플로우를 찾는 과정을 최단 거리 순으로 찾아나가면, 최소비용에 대한 최대 유량을 구할 수 있다
코드
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX_V 900
#define INF 1e9
using namespace std;
struct Edge {
int to, c, f, d;
Edge *r;
Edge() : Edge(-1, 0, 0) {}
Edge(int _to, int _c, int _d) : to(_to), c(_c), d(_d), f(0), r(NULL) {}
void addFlow(int _f) {
f += _f;
r->f -= _f;
}
int spare() {
return c - f;
}
};
vector<Edge*> adj[MAX_V];
void insertEdge(int u, int v, int w, int d) {
Edge *e1 = new Edge(v, w, d), *e2 = new Edge(u, 0, -d);
e1->r = e2;
e2->r = e1;
adj[u].push_back(e1);
adj[v].push_back(e2);
}
int main()
{
int n, m, i, j, k, l;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++) {
insertEdge(0, i + 1, 1, 0);
scanf("%d", &j);
while (j--) {
scanf("%d%d", &k, &l);
insertEdge(1 + i, 1 + n + k, 1, l);
}
}
for (i = 1; i <= m; i++)
insertEdge(1 + n + i, 1, 1, 0);
int S = 0, E = 1, result = 0, cost = 0;
while (1) {
queue<int> q;
int prev[MAX_V], dist[MAX_V];
bool inQ[MAX_V] = { 0 };
Edge *path[MAX_V] = { 0 };
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 v = q.front();
q.pop();
inQ[v] = false;
for (Edge *e : adj[v]) {
int next = e->to;
if (e->spare() > 0 && dist[next] > dist[v] + e->d) {
prev[next] = v;
path[next] = e;
dist[next] = dist[v] + e->d;
if (!inQ[next]) {
q.push(next);
inQ[next] = true;
}
}
}
}
if (prev[E] == -1)
break;
int flow = 1e9;
for (i = E; i != S; i = prev[i])
flow = min(flow, path[i]->spare());
for (i = E; i != S; i = prev[i]) {
path[i]->addFlow(flow);
cost += path[i]->d;
}
result += flow;
}
printf("%d\n%d", result, cost);
}
https://www.acmicpc.net/problem/11408 풀이
코드 템플릿 (C++11)
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX_V 2010
#define INF 0x7fffffff
using namespace std;
struct Edge {
int to, c, f, d;
Edge *r;
Edge() : Edge(-1, 0, 0) {}
Edge(int _to, int _c, int _d) : to(_to), c(_c), f(0), d(_d), r(NULL) {}
void addFlow(int _f) {
f += _f;
r->f -= _f;
}
int spare() {
return c - f;
}
};
void insertEdge(vector<Edge*> *adj, int u, int v, int w, int d) {
Edge *e1 = new Edge(v, w, d), *e2 = new Edge(u, 0, -d);
e1->r = e2;
e2->r = e1;
adj[u].push_back(e1);
adj[v].push_back(e2);
}
int mcmf(vector<Edge*> *adj, int S, int E) {
int cost = 0, k = 2;
while (k--) {
int prev[MAX_V], dist[MAX_V];
bool isQ[MAX_V] = { 0 };
Edge *path[MAX_V] = { 0 };
queue<int> q;
fill(prev, prev + MAX_V, -1);
fill(dist, dist + MAX_V, INF);
dist[S] = 0;
isQ[S] = true;
q.push(S);
while (!q.empty()) {
int curr = q.front();
q.pop();
isQ[curr] = false;
for (Edge *e : adj[curr]) {
int next = e->to;
if (e->spare() > 0 && dist[next] > dist[curr] + e->d) {
prev[next] = curr;
path[next] = e;
dist[next] = dist[curr] + e->d;
if (!isQ[next]) {
isQ[next] = true;
q.push(next);
}
}
}
}
if (prev[E] == -1)
break;
int flow = INF;
for (int i = E; i != S; i = prev[i])
flow = min(flow, path[i]->spare());
for (int i = E; i != S; i = prev[i]) {
path[i]->addFlow(flow);
cost += path[i]->d * flow;
}
}
return cost;
}
정리
- 정점을 단 한 번만 지나가게 하려면 -> 정점분할을 한 뒤(residual), 정점간의 간선 용량을 1로 설정
관련문제
https://www.acmicpc.net/problem/9413 제주도 관광 ★
https://www.acmicpc.net/problem/10937 두부 모판 자르기 ★