[BOJ] 백준 11406. 책 구매하기2 (Platinum IV) + Dinic(디닉) Algorithm

문제는 아래와 같다.

https://www.acmicpc.net/problem/11406

11406번: 책 구매하기 2

예전에 애드몬드 카프 알고리즘 공부 후, flow 기본문제들을 거의 다 풀어버린 줄 알았는데,

다행히 아직 안 푼 문제가 있어서 디닉을 적용해보았다.

---

의식의 흐름 및 해설

얼마나 많이 구매자들에게 책을 전달할 수 있을지,

그리고 구매자와 서점이 명확한 이분그래프 모양을 띄기 때문에 flow문제임을 확인할 수 있다.

 

N, M<=100이므로, 그리고 서점이 구매자에게 최대 얼마나 책을 판매할 수 있을지 구하는 문제이므로

Source: 서점, Sink: 구매자로 두고,

Source: 0번, 서점: 1~N, 구매자: 101~M , Sink: 201번으로 두고 디닉을 돌린다.

 

디닉의 시간복잡도는 O(V^2*E)이다.

 

한번 유량을 흘려보내줄 때마다, bfs로 level graph를 만드는데 O(E), 그리고 이 길이만큼 DFS를 돌릴 때, 최대 길이 O(V)만큼 O(E)번 augmenting path(증가경로)를 찾기 때문에 O(VE).

그리고 이 행동을 최대 O(V)번 반복하므로 (Sink 유량이 최대 V번을 초과하여 증가할 수 없기 때문에) 최종 시간복잡도는 O(V^2*E)인 것이다.

(dinic, flow 시간복잡도 관련 증명: https://koosaga.com/18)

 

근데 실제로는 훨씬 더 빨리 돌아가는 듯?

대충 O(V^2*E), O(V^4)이면 V가 200이어도 16e8이라 불안불안했는데 4ms밖에 걸리지 않았다.

E는 200^2 가 아닌 100^2 이므로 16e8이 아니라 4e8이어서 1초 내로 돌아가기 충분했다. 

요즘 컴퓨터는 특히 성능이 좋아서 1억번 연산 뿐만 아니라 2~3억번 정도도 1초 내로 돌아가기도 하고 말이다.

---

코드

// 211027 #11406 책구매하기2 Platinum IV
// flow dinic O(V^2*E) 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 223;
const double INF = 0x3f3f3f3f;
const int LNF = 1e16;
const int MOD = 1e9 + 7;
int N, M, a[MAX], b[MAX], lv[MAX], w[MAX], S = 0, E = 201;
struct Edge {
	int to, c, rev;
	Edge(int to, int c, int rev) :to(to), c(c), rev(rev) {}
};
vector<Edge> v[MAX];
void addEdge(int s, int e, int c) {
	v[s].push_back({ e,c,(int)v[e].size() });
	v[e].push_back({ s,0,(int)v[s].size() - 1 });
}
bool bfs() {
	memset(lv, -1, sizeof(lv));
	lv[S] = 0;
	queue<int> q;
	q.push(S);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto i : v[cur]) {
			if (i.c && lv[i.to] == -1) {
				lv[i.to] = lv[cur] + 1;
				q.push(i.to);
			}
		}
	}
	return lv[E] != -1;
}
int dfs(int cur, int c) {
	if (cur == E)return c;
	for (; w[cur] < v[cur].size(); w[cur]++) {
		Edge& e = v[cur][w[cur]];
		if (!e.c || lv[e.to] != lv[cur] + 1)
			continue;
		int f = dfs(e.to, min(c, e.c));
		if (f > 0) {
			e.c -= f;
			v[e.to][e.rev].c += f;
			return f;
		}
	}
	return 0;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	for (int i = 101; i <= N + 100; i++) {
		cin >> a[i];
		addEdge(i, E, a[i]);
	}
	for (int i = 1; i <= M; i++) {
		cin >> b[i];
		addEdge(S, i, b[i]);
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 101; j <= N + 100; j++) {
			int f;
			cin >> f;
			addEdge(i, j, f);
		}
	}
	int ans = 0;
	while (bfs()) {
		memset(w, 0, sizeof(w));
		while (1) {
			int c = dfs(S, INF);
			if (!c)break;
			ans += c;
		}
	}
	cout << ans << "\n";
}

---

애드몬드 카프로 풀지 말고 첨부터 디닉 쓸걸...