최대 유량 (Maximum Flow)
최대 유량 문제를 해결하기 위해 가장 널리 사용되는 Dinic 알고리즘의 구현입니다. 너비 우선 탐색(BFS)을 통해 레벨 그래프를 구성하고, 깊이 우선 탐색(DFS)을 통해 블로킹 유량(blocking flow)을 찾아내는 방식을 사용합니다. 현재 엣지 최적화(Current Edge Optimization)가 적용되어 시간 복잡도를 줄였습니다. 가독성과 유지보수를 위해 전역 배열 대신 객체 지향 기반의 인접 리스트(std::vector)를 사용합니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;
struct Edge {
int to, rev;
ll capacity;
};
struct Dinic {
int n;
vector<vector<Edge>> graph;
vector<int> level, iter;
Dinic(int n) : n(n), graph(n), level(n), iter(n) {}
void addEdge(int from, int to, ll cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& e : graph[v]) {
if (e.capacity > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
return level[t] >= 0;
}
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int& i = iter[v]; i < graph[v].size(); i++) {
Edge& e = graph[v][i];
if (e.capacity > 0 && level[v] < level[e.to]) {
ll d = dfs(e.to, t, min(f, e.capacity));
if (d > 0) {
e.capacity -= d;
graph[e.to][e.rev].capacity += d;
return d;
}
}
}
return 0;
}
ll maxFlow(int s, int t) {
ll flow = 0;
while (bfs(s, t)) {
fill(iter.begin(), iter.end(), 0);
ll d;
while ((d = dfs(s, t, INF)) > 0) {
flow += d;
}
}
return flow;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, s, t;
if (!(cin >> n >> m >> s >> t)) return 0;
Dinic dinic(n + 1);
for (int i = 0; i < m; i++) {
int u, v; ll w;
cin >> u >> v >> w;
dinic.addEdge(u, v, w);
}
cout << dinic.maxFlow(s, t) << "\n";
return 0;
}최소 비용 최대 유량 (Minimum Cost Maximum Flow)
최소 비용 최대 유량(MCMF) 문제는 최대 유량을 만족하는 흐름 중에서 간선 비용의 합이 최소가 되는 경우를 찾습니다. 주로 SPFA(Shortest Path Faster Algorithm)를 활용한 최단 경로 기반의 증가 경로 탐색을 사용하며, 음수 간선이 존재할 수 있는 환경에서도 올바르게 동작합니다.
1. 단일 경로 증가 방식 (SPFA 기반)
한 번에 하나의 증가 경로(Augmenting Path)를 찾아 유량을 흘려보내는 기본적인 MCMF 구현입니다. 벨만-포드 알고리즘의 큐 최적화 버전인 SPFA를 사용하여 최단 거리(최소 비용) 경로를 탐색합니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;
struct Edge {
int to, rev;
ll capacity, cost;
};
struct MCMF {
int n;
vector<vector<Edge>> graph;
vector<ll> dist;
vector<int> parentEdge, parentNode;
vector<bool> inQueue;
MCMF(int n) : n(n), graph(n), dist(n), parentEdge(n), parentNode(n), inQueue(n) {}
void addEdge(int from, int to, ll cap, ll cost) {
graph[from].push_back({to, (int)graph[to].size(), cap, cost});
graph[to].push_back({from, (int)graph[from].size() - 1, 0, -cost});
}
bool spfa(int s, int t) {
fill(dist.begin(), dist.end(), INF);
fill(inQueue.begin(), inQueue.end(), false);
queue<int> q;
dist[s] = 0;
inQueue[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
inQueue[u] = false;
for (int i = 0; i < graph[u].size(); i++) {
Edge& e = graph[u][i];
if (e.capacity > 0 && dist[u] + e.cost < dist[e.to]) {
dist[e.to] = dist[u] + e.cost;
parentNode[e.to] = u;
parentEdge[e.to] = i;
if (!inQueue[e.to]) {
inQueue[e.to] = true;
q.push(e.to);
}
}
}
}
return dist[t] != INF;
}
pair<ll, ll> solve(int s, int t) {
ll totalFlow = 0, totalCost = 0;
while (spfa(s, t)) {
ll bottleneck = INF;
for (int v = t; v != s; v = parentNode[v]) {
bottleneck = min(bottleneck, graph[parentNode[v]][parentEdge[v]].capacity);
}
for (int v = t; v != s; v = parentNode[v]) {
Edge& e = graph[parentNode[v]][parentEdge[v]];
e.capacity -= bottleneck;
graph[v][e.rev].capacity += bottleneck;
}
totalFlow += bottleneck;
totalCost += bottleneck * dist[t];
}
return {totalFlow, totalCost};
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, s, t;
if (!(cin >> n >> m >> s >> t)) return 0;
MCMF mcmf(n + 1);
for (int i = 0; i < m; i++) {
int u, v; ll w, c;
cin >> u >> v >> w >> c;
mcmf.addEdge(u, v, w, c);
}
auto [flow, cost] = mcmf.solve(s, t);
cout << flow << " " << cost << "\n";
return 0;
}2. 다중 경로 증가 방식 (ZKW / Dinic 기반)
Dinic 알고리즘의 다중 경로 탐색 아이디어를 MCMF에 적용한 방식입니다. SPFA로 최단 거리 레이어를 구성한 후, DFS를 통해 여러 경로를 동시에 탐색하여 유량을 흘려보냅니다. 단일 경로 방식보다 일반적으로 더 빠른 성능을 보이며, 대규모 그래프에서 유용합니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;
struct Edge {
int to, rev;
ll capacity, cost;
};
struct ZKW_MCMF {
int n;
vector<vector<Edge>> graph;
vector<ll> dist;
vector<int> iter;
vector<bool> visited;
ZKW_MCMF(int n) : n(n), graph(n), dist(n), iter(n), visited(n) {}
void addEdge(int from, int to, ll cap, ll cost) {
graph[from].push_back({to, (int)graph[to].size(), cap, cost});
graph[to].push_back({from, (int)graph[from].size() - 1, 0, -cost});
}
bool spfa(int s, int t) {
fill(dist.begin(), dist.end(), INF);
vector<bool> inQueue(n, false);
queue<int> q;
dist[s] = 0;
inQueue[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
inQueue[u] = false;
for (auto& e : graph[u]) {
if (e.capacity > 0 && dist[u] + e.cost < dist[e.to]) {
dist[e.to] = dist[u] + e.cost;
if (!inQueue[e.to]) {
inQueue[e.to] = true;
q.push(e.to);
}
}
}
}
return dist[t] != INF;
}
ll dfs(int u, int t, ll flow) {
if (u == t) return flow;
visited[u] = true;
ll pushed = 0;
for (int& i = iter[u]; i < graph[u].size(); i++) {
Edge& e = graph[u][i];
if (!visited[e.to] && e.capacity > 0 && dist[u] + e.cost == dist[e.to]) {
ll tr = dfs(e.to, t, min(flow - pushed, e.capacity));
if (tr > 0) {
e.capacity -= tr;
graph[e.to][e.rev].capacity += tr;
pushed += tr;
if (pushed == flow) break;
}
}
}
visited[u] = false;
return pushed;
}
pair<ll, ll> solve(int s, int t) {
ll totalFlow = 0, totalCost = 0;
while (spfa(s, t)) {
fill(iter.begin(), iter.end(), 0);
ll pushed;
while ((pushed = dfs(s, t, INF)) > 0) {
totalFlow += pushed;
totalCost += pushed * dist[t];
}
}
return {totalFlow, totalCost};
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, s, t;
if (!(cin >> n >> m >> s >> t)) return 0;
ZKW_MCMF zkw(n + 1);
for (int i = 0; i < m; i++) {
int u, v; ll w, c;
cin >> u >> v >> w >> c;
zkw.addEdge(u, v, w, c);
}
auto [flow, cost] = zkw.solve(s, t);
cout << flow << " " << cost << "\n";
return 0;
}