플로우 - Dinic, Edmonds-Karp 알고리즘

1. [ Dinic ] 

const int MAX = 808;
vector<int>g[MAX];
int work[MAX], lv[MAX], cap[MAX][MAX], flow[MAX][MAX];

struct Dinic {
	void add(int u, int v, int c) {
		g[u].push_back(v);
		g[v].push_back(u);
		cap[u][v] += c;
	}
	bool bfs(int S, int T) {
		memset(lv, -1, sizeof(lv));
		queue<int>q;
		lv[S] = 0;
		q.push(S);
		while (q.size()) {
			int cur = q.front(); q.pop();
			for (int nxt : g[cur]) {
				if (lv[nxt] == -1 && cap[cur][nxt] > flow[cur][nxt]) {
					lv[nxt] = lv[cur] + 1;
					q.push(nxt);
				}
			}
		}
		return ~lv[T];
	}
	int dfs(int cur, int w, int T) {
		if (cur == T) return w;
		for (int& i = work[cur]; i < g[cur].size(); i++) {
			int nxt = g[cur][i];
			if (lv[nxt] == lv[cur] + 1 && cap[cur][nxt] > flow[cur][nxt]) {
				int f = dfs(nxt, min(w, cap[cur][nxt] - flow[cur][nxt]), T);
				if (f) {
					flow[cur][nxt] += f;
					flow[nxt][cur] -= f;
					return f;
				}
			}
		}
		return 0;
	}
	int max_flow(int S, int T) {
		int ret = 0;
		while (bfs(S, T)) {
			memset(work, 0, sizeof(work));
			while (1) {
				int f = dfs(S, 1e9, T);
				if (!f) break;
				ret += f;
			}
		}
		return ret;
	}
}dinic;

 

 

 

 

2. [ Edmonds Karp]

 

const int MAX = 808;
vector<int>g[MAX];
cap[MAX][MAX], flow[MAX][MAX];

int max_flow(int S, int T) {
	int tot = 0;
	while (1) {
		int prev[MAX];
		memset(prev, -1, sizeof(prev));
		queue<int>q;
		q.push(S);
		while (q.size()) {
			int cur = q.front(); q.pop();
			for (int nxt : g[cur]) {
				if (prev[nxt] == -1 && cap[cur][nxt] > flow[cur][nxt]) {
					q.push(nxt);
					prev[nxt] = cur;
					if (nxt == T) break;
				}
			}
		}
		if (prev[T] == -1) break;
		int f = 1e9;
		for (int i = T; i != S; i = prev[i]) {
			f = min(f, cap[prev[i]][i] - flow[prev[i]][i]);
		}
		for (int i = T; i != S; i = prev[i]) {
			flow[prev[i]][i] += f;
			flow[i][prev[i]] -= f;
		}
		tot += f;
	}
	return tot;
}