최대 흐름 - Dinic 알고리즘¶
Dinic 알고리즘은 최대 흐름 문제를 $O(V^2E)$에 해결합니다. 최대 흐름 문제는 최대 흐름 - Ford-Fulkerson과 Edmonds-Karp 글에 정의되어 있습니다. 이 알고리즘은 1970년에 Yefim Dinitz가 발견했습니다.
정의¶
네트워크 $G$의 잔여 네트워크 $G^R$은 각 간선 $(v, u)\in G$마다 다음 두 간선을 포함하는 네트워크입니다:
- 용량이 $c_{vu}^R = c_{vu} - f_{vu}$인 $(v, u)$
- 용량이 $c_{uv}^R = f_{vu}$인 $(u, v)$
어떤 네트워크의 차단 흐름이란 $s$에서 $t$로 가는 모든 경로가 이 흐름에 의해 포화된 간선을 적어도 하나 포함하는 흐름입니다. 차단 흐름이 반드시 최대인 것은 아니라는 점에 유의하십시오.
네트워크 $G$의 계층 네트워크는 다음과 같은 방법으로 만든 네트워크입니다. 먼저 각 정점 $v$에 대해 $level[v]$, 즉 용량이 양수인 간선만 사용하여 $s$에서 이 정점까지 가는 (가중치 없는) 최단 경로를 계산합니다. 그다음 $level[v] + 1 = level[u]$를 만족하는 간선 $(v, u)$만 남깁니다. 이 네트워크에 사이클이 없다는 것은 자명합니다.
알고리즘¶
이 알고리즘은 여러 단계로 이루어집니다. 각 단계에서 $G$의 잔여 네트워크에 대한 계층 네트워크를 구성합니다. 그다음 계층 네트워크에서 임의의 차단 흐름을 찾아 현재 흐름에 더합니다.
정당성 증명¶
알고리즘이 종료되면 최대 흐름을 찾는다는 것을 보입시다.
알고리즘이 종료되었다면 계층 네트워크에서 차단 흐름을 찾지 못한 것입니다. 이는 계층 네트워크에 $s$에서 $t$로 가는 경로가 없다는 뜻입니다. 이는 잔여 네트워크에 $s$에서 $t$로 가는 경로가 없다는 뜻입니다. 이는 흐름이 최대라는 뜻입니다.
단계의 수¶
이 알고리즘은 $V$단계 미만에서 종료됩니다. 이를 증명하려면 먼저 두 가지 보조정리를 증명해야 합니다.
보조정리 1. 각 반복 후에 $s$에서 각 정점까지의 거리는 감소하지 않습니다. 즉, $level_{i+1}[v] \ge level_i[v]$입니다.
증명. 단계 $i$와 정점 $v$를 고정합니다. $G_{i+1}^R$에서 $s$에서 $v$로 가는 임의의 최단 경로 $P$를 생각해 봅시다. $P$의 길이는 $level_{i+1}[v]$와 같습니다. $G_{i+1}^R$에는 $G_i^R$의 간선과 $G_i^R$의 간선에 대한 역방향 간선만 포함될 수 있다는 점에 주목하십시오. $P$에 $G_i^R$에 대한 역방향 간선이 없다면, $P$는 $G_i^R$에서의 경로이기도 하므로 $level_{i+1}[v] \ge level_i[v]$입니다. 이제 $P$에 역방향 간선이 적어도 하나 있다고 가정합시다. 그러한 첫 번째 간선을 $(u, w)$라고 합시다. 그러면 (첫 번째 경우에 의해) $level_{i+1}[u] \ge level_i[u]$입니다. 간선 $(u, w)$는 $G_i^R$에 속하지 않으므로, 간선 $(w, u)$는 이전 반복에서 차단 흐름의 영향을 받았습니다. 이는 $level_i[u] = level_i[w] + 1$임을 의미합니다. 또한 $level_{i+1}[w] = level_{i+1}[u] + 1$입니다. 이 두 방정식과 $level_{i+1}[u] \ge level_i[u]$로부터 $level_{i+1}[w] \ge level_i[w] + 2$를 얻습니다. 이제 경로의 나머지 부분에 대해서도 같은 아이디어를 적용할 수 있습니다.
보조정리 2. $level_{i+1}[t] > level_i[t]$
증명. 앞의 보조정리로부터 $level_{i+1}[t] \ge level_i[t]$입니다. $level_{i+1}[t] = level_i[t]$라고 가정합시다. $G_{i+1}^R$에는 $G_i^R$의 간선과 $G_i^R$의 간선에 대한 역방향 간선만 포함될 수 있다는 점에 주목하십시오. 이는 $G_i^R$에 차단 흐름에 의해 막히지 않은 최단 경로가 존재한다는 것을 의미합니다. 이는 모순입니다.
이 두 보조정리로부터, $level[t]$는 증가하지만 $V - 1$보다 커질 수 없으므로 단계의 수는 $V$보다 적다는 결론을 얻습니다.
차단 흐름 찾기¶
각 반복에서 차단 흐름을 찾으려면, 계층 네트워크에서 흐름을 더 보낼 수 있는 동안 DFS로 $s$에서 $t$로 흐름을 보내 보면 됩니다. 이를 더 빠르게 하려면, 더 이상 흐름을 보내는 데 사용할 수 없는 간선을 제거해야 합니다. 이를 위해 각 정점마다 다음으로 사용할 수 있는 간선을 가리키는 포인터를 유지할 수 있습니다.
DFS 한 번의 실행에는 $O(k+V)$ 시간이 걸리며, 여기서 $k$는 이번 실행에서 포인터가 전진한 횟수입니다. 모든 실행에 걸쳐 합하면 포인터가 전진한 횟수는 $E$를 넘을 수 없습니다. 한편, 매 실행마다 적어도 하나의 간선이 포화되므로 전체 실행 횟수는 $E$를 넘지 않습니다. 따라서 차단 흐름을 찾는 전체 실행 시간은 $O(VE)$입니다.
복잡도¶
단계의 수가 $V$보다 적으므로 전체 복잡도는 $O(V^2E)$입니다.
단위 네트워크¶
단위 네트워크란 $s$와 $t$를 제외한 모든 정점에 대해 들어오는 간선 또는 나가는 간선이 유일하며 용량이 1인 네트워크입니다. 흐름으로 최대 매칭 문제를 풀기 위해 만드는 네트워크가 바로 이 경우에 해당합니다.
단위 네트워크에서 Dinic 알고리즘은 $O(E\sqrt{V})$에 동작합니다. 이를 증명해 봅시다.
첫째, 각 간선은 최대 한 번만 고려되므로 이제 각 단계는 $O(E)$에 동작합니다.
둘째, 이미 $\sqrt{V}$번의 단계가 진행되었다고 가정합시다. 그러면 길이가 $\le\sqrt{V}$인 증가 경로는 모두 찾은 상태입니다. $f$를 현재 흐름, $f'$를 최대 흐름이라고 합시다. 둘의 차 $f' - f$를 생각해 봅시다. 이는 $G^R$에서 값이 $|f'| - |f|$인 흐름이며, 각 간선에서 $0$ 또는 $1$의 값을 가집니다. 이 흐름은 $s$에서 $t$로 가는 $|f'| - |f|$개의 경로와, 경우에 따라 몇 개의 사이클로 분해할 수 있습니다. 네트워크가 단위 네트워크이므로 이 경로들은 공통 정점을 가질 수 없습니다. 따라서 전체 정점 수는 $\ge (|f'| - |f|)\sqrt{V}$이지만 동시에 $\le V$이기도 하므로, 추가로 $\sqrt{V}$번 반복하면 반드시 최대 흐름을 찾게 됩니다.
단위 용량 네트워크¶
모든 간선의 용량이 단위 용량이지만 들어오는 간선과 나가는 간선의 수에는 제한이 없는 더 일반적인 상황에서는, 경로들이 공통 정점이 아니라 공통 간선을 가질 수 없습니다. 비슷한 방식으로 반복 횟수의 상한이 $\sqrt E$임을 증명할 수 있으므로, 이러한 네트워크에서 Dinic 알고리즘의 실행 시간은 최대 $O(E \sqrt E)$입니다.
마지막으로, 단위 용량 네트워크에서 단계 수가 $O(V^{2/3})$를 넘지 않는다는 것도 증명할 수 있으며, 이는 간선 수가 특히 많은 네트워크에서 $O(EV^{2/3})$라는 또 다른 상한을 제공합니다.
구현¶
struct FlowEdge {
int v, u;
long long cap, flow = 0;
FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};
struct Dinic {
const long long flow_inf = 1e18;
vector<FlowEdge> edges;
vector<vector<int>> adj;
int n, m = 0;
int s, t;
vector<int> level, ptr;
queue<int> q;
Dinic(int n, int s, int t) : n(n), s(s), t(t) {
adj.resize(n);
level.resize(n);
ptr.resize(n);
}
void add_edge(int v, int u, long long cap) {
edges.emplace_back(v, u, cap);
edges.emplace_back(u, v, 0);
adj[v].push_back(m);
adj[u].push_back(m + 1);
m += 2;
}
bool bfs() {
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : adj[v]) {
if (edges[id].cap == edges[id].flow)
continue;
if (level[edges[id].u] != -1)
continue;
level[edges[id].u] = level[v] + 1;
q.push(edges[id].u);
}
}
return level[t] != -1;
}
long long dfs(int v, long long pushed) {
if (pushed == 0)
return 0;
if (v == t)
return pushed;
for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
int id = adj[v][cid];
int u = edges[id].u;
if (level[v] + 1 != level[u])
continue;
long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
if (tr == 0)
continue;
edges[id].flow += tr;
edges[id ^ 1].flow -= tr;
return tr;
}
return 0;
}
long long flow() {
long long f = 0;
while (true) {
fill(level.begin(), level.end(), -1);
level[s] = 0;
q.push(s);
if (!bfs())
break;
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, flow_inf)) {
f += pushed;
}
}
return f;
}
};