디닉의 알고리즘 Dinic's Algorithm

대표적인 최대 유량 알고리즘이다. 정점의 개수를 $V$, 간선의 개수를 $E$, 최대 유량(답)을 $f$라 할 때, $O(fE)$ 또는 $O(V^2E)$에 동작한다. 간선의 유량이 모두 같을 경우(모두 0 또는 1), 신기하게도 $O(min(V^{2/3}E, V^{3/2}))$에 동작한다.

직접적인 flow문제는 별로 없고, 최댓값을 구하는 문제를 max flow로 환원할 수 있는 경우가 종종 있다. 혹은 최솟값을 구하는 문제를 min cut으로 환원하기도 한다. 

 

아래 링크들을 보고 공부하였다.

https://jason9319.tistory.com/150

https://koosaga.com/18

https://koosaga.com/133

 

내 코드

#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back

struct EDGE {
	int v, c, r;				// vertex, capacity, reverse
	EDGE(int v, int c, int r) : v(v), c(c), r(r) {}
};

vector<EDGE> ed[MAXN];
int w[MAXN], lvl[MAXN];
int S, E;

void addedge(int a, int b, int c) {		//a->b로 유량 c인 간선 연결
	ed[a].eb(b, c, ed[b].size());
	ed[b].eb(a, 0, ed[a].size() - 1);
}

bool bfs() {					//각 정점의 level을 구한다. lvl[S] = 1
	memset(lvl, 0, sizeof(lvl));
	lvl[S] = 1;
	queue<int> q;
	q.push(S);
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		for(auto &a : ed[t]) if(a.c && !lvl[a.v]) {
			lvl[a.v] = lvl[t] + 1;
			q.push(a.v);
		}
	}
	return lvl[E];
}

int dfs(int x, int c) {		//정점 x로 유량 c가 들어올 때, sink까지 흐를 수 있는 최대 유량을 구한다
	if(x == E) return c;
	for(; w[x] < ed[x].size(); w[x]++) {
		EDGE &e = ed[x][w[x]];
		if(!e.c || lvl[e.v] != lvl[x] + 1) continue;
		int f = dfs(e.v, min(c, e.c));
		if(f) {
			e.c -= f;
			ed[e.v][e.r].c += f;
			return f;
		}
	}
	return 0;
}

int main() {
	//TODO	
	int ans = 0;
	while(bfs()) {
		memset(w, 0, sizeof(w));
		while(1) {
			int c = dfs(S, INF);
			if(!c) break;
			ans += c;
		}
	}
	//TODO
}