에드몬드 카프 알고리즘
while 증강 경로 존재:
BFS로 증강 경로 하나 찾기
그 경로로 유량 보내기디닉 알고리즘
-
실전 최대유량 기본 알고리즘
디닉 알고리즘(Dinic’s algorithm) 에서는 BFS로 레벨 그래프를 만들고, 레벨이 증가하는 간선만 따라 DFS로 가능한 유량을 최대한 흘려 blocking flow 를 만든다. 한 번의 단계가 끝날 때마다 도착점의 레벨이 증가하므로 단계 수가 제한되며, 일반 그래프에서 시간 복잡도는 가 된다.
while BFS로 레벨 그래프를 만들 수 있으면:
while DFS로 레벨 그래프 안에서 유량을 보낼 수 있으면:
가능한 만큼 유량을 보낸다.시간복잡도
Dinic은 BFS로 레벨 그래프를 만든 뒤, 현재 레벨 그래프에서 가능한 경로들을 DFS로 최대한 사용해 blocking flow를 만든다. 한 phase가 끝나면 현재 최단거리의 증강 경로들이 모두 막히므로, 다음 BFS에서 sink의 레벨은 증가한다. 따라서 phase는 최대 O(V)번 진행된다.
V: blocking flow 이후 sink의 레벨이 증가하므로, 레벨 그래프를 다시 만드는 최대 phase 수V: DFS로 한 증강 경로를 따라갈 때의 최대 경로 길이E: 한 phase에서 포화시키며 처리할 수 있는 최대 간선 수
요약
- BFS로 잔여 용량이 있는 간선만 탐색하여 S를 기준으로 각 정점의 레벨을 정하고 레벨 그래프를 만든다.
- 레벨이 정확히 +1 증가하는 간선만 따라가며 DFS로 유량을 흘린다.
- 한 번 만든 레벨 그래프에서 가능한 유량을 최대한 흘려 blocking flow를 만든다.
- 더 이상 흘릴 수 없으면 다시 BFS를 수행해, 변경된 잔여 그래프를 기준으로 새로운 레벨 그래프 를 만든다. (1번부터 다시 반복)
- 일반 그래프 기준 시간복잡도는 이며, 실제 대회에서는 에드몬드 카프보다 훨씬 빠른 경우가 많다.
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
class Dinic {
private:
struct Edge {
int to; // 도착 정점
int rev; // 역방향 간선 인덱스
ll cap; // 잔여 용량
};
int n;
vector<vector<Edge>> graph;
vector<int> level;
vector<int> work;
// BFS: 잔여 용량이 있는 간선으로 레벨 그래프 생성
bool bfs(int source, int sink) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[source] = 0;
q.push(source);
while (!q.empty()) {
int u = q.front();
q.pop();
for (const Edge& edge : graph[u]) {
int v = edge.to;
if (edge.cap > 0 && level[v] == -1) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[sink] != -1;
}
// DFS: 현재 레벨 그래프에서 유량 보내기
ll dfs(int u, int sink, ll flow) {
// sink 도착
if (u == sink) {
return flow;
}
// current arc optimization
while (work[u] < (int)graph[u].size()) {
int i = work[u];
Edge& edge = graph[u][i];
int v = edge.to;
int rev = edge.rev;
ll cap = edge.cap;
// 잔여 용량이 있고,
// 레벨이 정확히 +1 증가하는 간선만 사용
if (cap > 0 && level[v] == level[u] + 1) {
// 현재까지 가능한 유량과
// 이 간선의 잔여 용량 중 작은 값 전달
ll amount = dfs(
v,
sink,
min(flow, cap)
);
// 유량을 보낼 수 있었다면
if (amount > 0) {
// 정방향 잔여 용량 감소
edge.cap -= amount;
// 역방향 잔여 용량 증가
graph[v][rev].cap += amount;
return amount;
}
}
// 이 간선으로는 더 이상 유량을 못 보냄
// 다음 간선 확인
work[u]++;
}
return 0;
}
public:
Dinic(int n)
: n(n),
graph(n),
level(n),
work(n) {
}
void add_edge(int u, int v, ll cap) {
// forward.rev
// = graph[v]에서 backward가 들어갈 위치
Edge forward = {
v,
(int)graph[v].size(),
cap
};
// backward.rev
// = graph[u]에서 forward가 들어갈 위치
Edge backward = {
u,
(int)graph[u].size(),
0
};
graph[u].push_back(forward);
graph[v].push_back(backward);
}
ll max_flow(int source, int sink) {
ll total_flow = 0;
// BFS로 sink까지 갈 수 있는 동안 반복
while (bfs(source, sink)) {
// current arc optimization
fill(work.begin(), work.end(), 0);
// 현재 레벨 그래프에서
// blocking flow가 될 때까지 반복
while (true) {
ll amount = dfs(
source,
sink,
INF
);
// 현재 레벨 그래프에서
// 더 이상 유량을 보낼 수 없음
if (amount == 0) {
break;
}
total_flow += amount;
}
}
return total_flow;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// --------------------------------------------------
// 테스트 그래프
// --------------------------------------------------
int n = 6;
vector<tuple<int, int, ll>> edges = {
{0, 1, 12}, // 1 -> 2
{0, 3, 11}, // 1 -> 4
{1, 2, 6}, // 2 -> 3
{1, 3, 3}, // 2 -> 4
{1, 4, 5}, // 2 -> 5
{1, 5, 9}, // 2 -> 6
{2, 5, 8}, // 3 -> 6
{3, 4, 9}, // 4 -> 5
{4, 2, 3}, // 5 -> 3
{4, 5, 4}, // 5 -> 6
};
int source = 0;
int sink = 5;
Dinic dinic(n);
for (auto [u, v, cap] : edges) {
dinic.add_edge(u, v, cap);
}
cout << dinic.max_flow(source, sink) << '\n';
/*
// --------------------------------------------------
// 실제 입력
// --------------------------------------------------
int n, m;
cin >> n >> m;
Dinic dinic(n);
for (int i = 0; i < m; ++i) {
int u, v;
ll cap;
cin >> u >> v >> cap;
// 1-based 입력이라면
// --u;
// --v;
dinic.add_edge(u, v, cap);
}
int source, sink;
cin >> source >> sink;
// 1-based 입력이라면
// --source;
// --sink;
cout << dinic.max_flow(source, sink) << '\n';
*/
return 0;
}python
from collections import deque
import sys
sys.setrecursionlimit(10**6)
INF = 10**18
class Dinic:
def __init__(self, n):
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, u, v, cap):
# edge = [도착점, 역방향 간선 인덱스, 잔여 용량]
forward = [v, len(self.graph[v]), cap]
backward = [u, len(self.graph[u]), 0]
self.graph[u].append(forward)
self.graph[v].append(backward)
# BFS: 잔여 용량이 있는 간선으로 레벨 그래프 생성
def bfs(self, source, sink):
self.level = [-1] * self.n
self.level[source] = 0
q = deque([source])
while q:
u = q.popleft()
for v, rev, cap in self.graph[u]:
if cap > 0 and self.level[v] == -1:
self.level[v] = self.level[u] + 1
q.append(v)
return self.level[sink] != -1
# DFS: 현재 레벨 그래프에서 유량 보내기
def dfs(self, u, sink, flow):
# sink 도착
if u == sink:
return flow
# current arc optimization
while self.work[u] < len(self.graph[u]):
i = self.work[u]
# edge = [도착점, 역방향 간선 인덱스, 잔여 용량]
edge = self.graph[u][i]
v, rev, cap = edge
# 잔여 용량이 있고,
# 레벨이 정확히 +1 증가하는 간선만 사용
if cap > 0 and self.level[v] == self.level[u] + 1:
# 현재까지 가능한 유량과
# 이 간선의 잔여 용량 중 작은 값 전달
amount = self.dfs(
v,
sink,
min(flow, cap)
)
# 유량을 보낼 수 있었다면
if amount > 0:
# 정방향 잔여 용량 감소
edge[2] -= amount
# 역방향 잔여 용량 증가
self.graph[v][rev][2] += amount
return amount
# 이 간선으로는 더 이상 유량을 못 보냄
# 다음 간선을 확인
self.work[u] += 1
# u에서 sink 방향으로 더 이상 갈 수 없음
return 0
def max_flow(self, source, sink):
total_flow = 0
# BFS가 sink에 도달할 수 있는 동안 반복
while self.bfs(source, sink):
# current arc optimization
# 각 정점에서 다음에 확인할 간선 위치
self.work = [0] * self.n
# 현재 레벨 그래프에서
# 더 이상 유량을 못 보낼 때까지 반복
while True:
amount = self.dfs(source, sink, INF)
# blocking 상태
if amount == 0:
break
total_flow += amount
return total_flow
# --------------------------------------------------
# 테스트 그래프
# --------------------------------------------------
n = 6
edges = [
(0, 1, 12), # 1 -> 2
(0, 3, 11), # 1 -> 4
(1, 2, 6), # 2 -> 3
(1, 3, 3), # 2 -> 4
(1, 4, 5), # 2 -> 5
(1, 5, 9), # 2 -> 6
(2, 5, 8), # 3 -> 6
(3, 4, 9), # 4 -> 5
(4, 2, 3), # 5 -> 3
(4, 5, 4), # 5 -> 6
]
source = 0
sink = 5
dinic = Dinic(n)
for u, v, cap in edges:
dinic.add_edge(u, v, cap)
print(dinic.max_flow(source, sink))
"""
# 실제 입력
n, m = map(int, input().split())
dinic = Dinic(n)
for _ in range(m):
u, v, cap = map(int, input().split())
# 1-based 입력이라면
# u -= 1
# v -= 1
dinic.add_edge(u, v, cap)
source, sink = map(int, input().split())
# 1-based 입력이라면
# source -= 1
# sink -= 1
print(dinic.max_flow(source, sink))
"""