개요
네트워크 플로우는 그래프 이론에서 중요한 주제로, 유량이 흐르는 시스템을 모델링하는 데 사용된다. 예를 들어 수도 공급망을 생각해보자. 수원지(s)에서 물이 나와 각 파이프를 통해 소비지점(t)에 도달한다. 각 파이프는 단위 시간당 허용되는 최대 유량(용량)을 가지며, 목표는 전체 시스템에서 t로 흘러들어가는 물의 양을 최대화하는 것이다. 이 문제는 최대 유량 문제로 알려져 있으며, 다양한 알고리즘을 통해 해결할 수 있다.
기본 개념
1. 네트워크
유량이 흐르는 방향성 그래프 \( G = (V, E) \)를 고려하자. 각 간선 \( (u, v) \)는 용량 \( c(u,v) \)를 가지며, 두 특별한 정점인 출발점(source, s)과 도착점(sink, t)이 존재한다. 이를 네트워크라고 한다.
2. 유량 함수 (Flow)
유량 \( f(u,v) \)는 다음 조건을 만족해야 한다:
- 용량 제한: \( f(u,v) \leq c(u,v) \)
- 반대칭성: \( f(u,v) = -f(v,u) \)
- 보존 법칙: \( s \)와 \( t \)를 제외한 모든 정점 \( u \)에 대해, 유입량 = 유출량
3. 잔여 그래프 (Residual Graph)
현재 유량 상태에서 추가로 흐릴 수 있는 여유가 있는 간선들로 구성된 그래프이다. 잔여 용량은 \( c_f(u,v) = c(u,v) - f(u,v) \)로 계산되며, 역방향 간선에는 \( f(u,v) \)만큼의 용량이 추가된다. 이를 통해 "유량 회수" 즉, 경로 변경이 가능해진다.
4. 증가 경로 (Augmenting Path)
잔여 그래프에서 \( s \)에서 \( t \)까지 잔여 용량이 양수인 경로. 이 경로를 따라 유량을 증가시킬 수 있다.
최대 유량 알고리즘
Edmonds-Karp 알고리즘
기본적인 접근 방식으로, BFS를 사용하여 잔여 그래프에서 가장 짧은 증가 경로를 반복적으로 찾는다. 매번 경로를 찾아 그 경로 상의 최소 잔여 용량만큼 유량을 증가시키고, 역방향 간선에 유량을 반영한다.
시간 복잡도는 \( O(VE^2) \)이며, 실제 동작에서는 대체로 빠르게 동작한다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
const int INF = 1e9;
struct Edge {
int to, cap, rev;
Edge(int t, int c, int r) : to(t), cap(c), rev(r) {}
};
vector<Edge> graph[MAXN];
int parent[MAXN], edgeIndex[MAXN];
void addEdge(int u, int v, int cap) {
graph[u].emplace_back(v, cap, graph[v].size());
graph[v].emplace_back(u, 0, graph[u].size() - 1);
}
bool bfs(int s, int t) {
fill(parent, parent + MAXN, -1);
queue<int> q;
q.push(s);
parent[s] = s;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < graph[u].size(); ++i) {
auto& e = graph[u][i];
if (parent[e.to] == -1 && e.cap > 0) {
parent[e.to] = u;
edgeIndex[e.to] = i;
if (e.to == t) return true;
q.push(e.to);
}
}
}
return false;
}
int edmondsKarp(int s, int t) {
int totalFlow = 0;
while (bfs(s, t)) {
int flow = INF;
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
int idx = edgeIndex[v];
flow = min(flow, graph[u][idx].cap);
}
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
int idx = edgeIndex[v];
graph[u][idx].cap -= flow;
int revIdx = graph[u][idx].rev;
graph[v][revIdx].cap += flow;
}
totalFlow += flow;
}
return totalFlow;
}
Dinic 알고리즘
Edmonds-Karp의 개선 버전으로, 성능이 우수하여 실무 및 알고리즘 대회에서 더 자주 사용된다. 다음과 같은 전략을 사용한다:
- BFS 계층 분할: 각 정점까지의 거리를 계산하여 계층 구조를 형성하고, DFS 시 한 방향으로만 진행하도록 한다.
- 다중 경로 확장 (Multi-path DFS): 하나의 DFS 호출 내에서 여러 경로를 탐색하여 유량을 누적한다.
- 현재 간선 최적화 (Current Arc Optimization): 이미 처리한 간선을 다시 탐색하지 않도록 포인터를 유지한다.
시간 복잡도는 \( O(V^2E) \)이며, 일반적인 경우 매우 효율적이다.
int level[MAXN], ptr[MAXN];
bool dinicBFS(int s, int t) {
fill(level, level + MAXN, -1);
queue<int> q;
q.push(s);
level[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& e : graph[u]) {
if (level[e.to] == -1 && e.cap > 0) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return level[t] != -1;
}
int dfs(int u, int t, int flow) {
if (u == t || flow == 0) return flow;
for (int& i = ptr[u]; i < graph[u].size(); ++i) {
auto& e = graph[u][i];
if (level[e.to] == level[u] + 1 && e.cap > 0) {
int pushed = dfs(e.to, t, min(flow, e.cap));
if (pushed > 0) {
e.cap -= pushed;
graph[e.to][e.rev].cap += pushed;
return pushed;
}
}
}
return 0;
}
int dinic(int s, int t) {
int totalFlow = 0;
while (dinicBFS(s, t)) {
fill(ptr, ptr + MAXN, 0);
while (int pushed = dfs(s, t, INF)) {
totalFlow += pushed;
}
}
return totalFlow;
}
최소 컷 (Min-Cut)
그래프를 \( s \)와 \( t \)를 각각 포함하는 두 집합 \( S \)와 \( T \)로 나누는 것을 컷이라 하고, \( S \)에서 \( T \)로 향하는 간선들의 용량 합을 컷의 용량이라 한다. 최소 컷은 그러한 컷 중 용량이 가장 작은 것이다.
최대 유량 = 최소 컷이라는 유명한 정리가 존재하며, 이는 최대 유량을 구하면 자동으로 최소 컷도 구할 수 있음을 의미한다. 이 정리는 유량 보존 법칙과 선형 계획 쌍대성 등을 통해 증명 가능하다.
비용 유량 (Minimum Cost Maximum Flow)
각 간선에 유량 1단위당 발생하는 비용 \( cost(u,v) \)가 주어질 때, 최대 유량을 흘리면서 전체 비용을 최소화하는 문제이다. Edmonds-Karp 알고리즘의 증가 경로 선택 방식을 수정하여, 비용이 가장 적은 경로를 우선적으로 선택하면 된다.
이를 위해 잔여 그래프에서 가중치가 음수일 수 있으므로, SPFA 또는 Bellman-Ford를 사용하여 최단 경로를 찾는다. 이후 해당 경로로 유량을 흘리고, 과정을 반복한다.
struct CostEdge {
int to, cap, cost, rev;
};
vector<CostEdge> costGraph[MAXN];
int dist[MAXN], inQueue[MAXN], prevNode[MAXN], prevEdge[MAXN];
bool spfa(int s, int t) {
fill(dist, dist + MAXN, INT_MAX);
memset(inQueue, 0, sizeof(inQueue));
queue<int> q;
q.push(s);
dist[s] = 0;
inQueue[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
inQueue[u] = 0;
for (int i = 0; i < costGraph[u].size(); ++i) {
auto& e = costGraph[u][i];
if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
prevNode[e.to] = u;
prevEdge[e.to] = i;
if (!inQueue[e.to]) {
q.push(e.to);
inQueue[e.to] = 1;
}
}
}
}
return dist[t] != INT_MAX;
}
pair<int, int> minCostMaxFlow(int s, int t) {
int totalFlow = 0, totalCost = 0;
while (spfa(s, t)) {
int flow = INT_MAX;
for (int v = t; v != s; v = prevNode[v]) {
int u = prevNode[v];
int idx = prevEdge[v];
flow = min(flow, costGraph[u][idx].cap);
}
for (int v = t; v != s; v = prevNode[v]) {
int u = prevNode[v];
int idx = prevEdge[v];
costGraph[u][idx].cap -= flow;
int rev = costGraph[u][idx].rev;
costGraph[v][rev].cap += flow;
totalCost += flow * costGraph[u][idx].cost;
}
totalFlow += flow;
}
return {totalFlow, totalCost};
}
응용 및 문제 추천
네트워크 플로우는 매칭 문제, 생산-소비 모델, 이미지 분할 등 다양한 분야에 응용된다. 대표적인 연습 문제집으로는 "Network Flow 24 Problems"가 있으며, 이는 다양한 변형과 응용을 다룬다.