최대 유량 - 디닉

jason9319.tistory.com/150

blog.naver.com/kks227/220808685331

 

위 두 블로그에서 공부했습니다. 특히 코드는 jason님의 코드를 많이 참고했습니다.

 

---

$O(V^2E)$

 

1. bfs로 각 정점마다 소스로부터 얼마나 떨어져있는지 의미하는 level 배열을 초기화 해준다.

 

싱크에 도달할 수 있다면

2. 소스-싱크 경로상 차단 유량을 구해준다. dfs에 지금까지 최소 유량을 같이 보내주고 반환값을 이후 최소 유량으로 설정하면 쉽게 구할 수 있다.

 

차단 유량이 0보다 크다면 반복한다.

 

 

 

dfs할 때 역방향 간선 때문에 한 정점을 여러번 접근할 수 있다. work배열로 정점 u를 여러 번 접근하더라도 dfs 진행에 있어서 다음 정점 v를 중복해서 접근하지 않도록 한다.

 

 

 

<문제>

www.acmicpc.net/problem/6086

 

<코드>

const int MAX = 52;
const int INF = 1e9;

int m, c[MAX][MAX], level[MAX], work[MAX];
vector<int> g[MAX];

int ctoi(char c) {
	if (c <= 'Z') return c - 'A';
	return c - 'a' + 26;
}
int src = ctoi('A'), snk = ctoi('Z');

bool bfs() {
	memset(level, -1, sizeof(level));
	queue<int> q;
	q.push(src);
	level[src] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : g[u]) {
			if (level[v] == -1 && c[u][v] > 0) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return level[snk] != -1;
}

int dfs(int u, int ret) {
	if (u == snk) return ret;

	for (int& i = work[u], v; i < g[u].size(); i++) {
		v = g[u][i];
		if (level[v] == level[u] + 1 && c[u][v] > 0) {
			int tmp = dfs(v, min(ret, c[u][v]));
			if (tmp > 0) {
				c[u][v] -= tmp;
				c[v][u] += tmp;
				return tmp;
			}
		}
	}
	return 0;
}

int main() {
	FAST; cin >> m;
	for (int i = 0, u, v, w; i < m; i++) {
		char x, y; cin >> x >> y >> w;
		u = ctoi(x), v = ctoi(y);
		c[u][v] = c[v][u] += w;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	int tot = 0;
	while (bfs()) {
		memset(work, 0, sizeof(work));
		int flow;
		while (flow = dfs(src, INF)) tot += flow;
	}
	cout << tot << '\n';
}

 

 

---

<문제>

www.acmicpc.net/problem/2188

축사배정 매칭문제

 

<코드>

const int MAX = 405;
const int INF = 1e9;

int n, m, st=0, en;
int level[MAX], work[MAX], c[MAX][MAX];
vector<int> g[MAX];

bool bfs() {
	memset(level, -1, sizeof(level));
	queue<int> q;
	q.push(st);
	level[st] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : g[u]) {
			if (level[v] == -1 && c[u][v] > 0) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return level[en] != -1;
}

int dfs(int u, int ret) {
	if (u == en) return ret;

	for (int& i = work[u]; i < g[u].size(); i++) {
		int v = g[u][i];
		if (c[u][v] > 0 && level[v] == level[u] + 1) {
			int tmp = dfs(v, min(ret, c[u][v]));
			if (tmp > 0) {
				c[u][v] -= tmp;
				c[v][u] += tmp;
				return tmp;
			}
		}
	}
	return 0;
}

int main() {
	FAST; cin >> n >> m;
	en = n + m + 1;
	for (int u = 1; u <= n; u++) {
		int cnt; cin >> cnt;
		g[0].push_back(u);
		g[u].push_back(0);
		c[0][u] = 1;
		while (cnt--) {
			int v; cin >> v;
			v += n;
			g[u].push_back(v);
			g[v].push_back(u);
			c[u][v] = 1;
		}
	}
	for (int u = n + 1; u <= n + m; u++) {
		g[u].push_back(en);
		g[en].push_back(u);
		c[u][en] = 1;
	}

	int ans = 0;
	while (bfs()) {
		memset(work, 0, sizeof(work));
		int flow;
		while (flow = dfs(st, INF)) ans += flow;
	}
	cout << ans << '\n';
}