[BOJ] 백준 15892 사탕 줍는 로봇

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

로봇은 사탕이 있는 길로만 이동할 수 있으며, 그 길을 지나갈 때 사탕을 딱 하나만 주워간다.

사탕을 간선의 용량으로 보고, 로봇이 길을 지나는 것을 그 간선에 유량이 1씩 흐르는 것으로 보면 기본적인 네트워크 플로우 문제이다. 

세팅할 수 있는 로봇의 최대 수는 그래프에서 흐를 수 있는 최대유량과 같다.

정답 코드

	#include <iostream>
	#include <queue>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	#define INF 0x3f3f3f3f
	struct MaxFlow {
	struct Edge {
	int to, cap;
	Edge *rev;
	Edge(int t, int c) :to(t), cap(c), rev(NULL) {}
	};
	int n, src, sink;
	vector<vector<Edge*>> p;
	vector<int> level, work;
	MaxFlow(int n, int s, int t) :n(n), src(s), sink(t) {
	p.resize(n + 1);
	}
	void add_edge(int u, int v, int cap) {
	Edge *ori = new Edge(v, cap);
	Edge *rev = new Edge(u, 0);
	ori->rev = rev;
	rev->rev = ori;
	p[u].push_back(ori);
	p[v].push_back(rev);
	}
	int flow() {
	int ans = 0;
	while (bfs()) {
	work = vector<int>(n + 1);
	int f = 0;
	while (f = dfs(src, INF))
	ans += f;
	}
	return ans;
	}
	bool bfs() {
	level = vector<int>(n + 1, -1);
	queue<int> q;
	q.push(src);
	level[src] = 0;
	while (!q.empty()) {
	int now = q.front();
	q.pop();
	for (auto e : p[now]) {
	int next = e->to;
	int ncap = e->cap;
	if (ncap > 0 && level[next] == -1) {
	level[next] = level[now] + 1;
	q.push(next);
	}
	}
	}
	return level[sink] != -1;
	}
	int dfs(int now, int c) {
	if (now == sink) {
	return c;
	}
	for (int &i = work[now]; i < p[now].size(); i++) {
	auto e = p[now][i];
	int next = e->to;
	int ncap = e->cap;
	if (level[next] == level[now] + 1 && ncap > 0) {
	int f = dfs(next, min(ncap, c));
	if (f) {
	e->cap -= f;
	e->rev->cap += f;
	return f;
	}
	}
	}
	return 0;
	}
	};
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	MaxFlow mf(n, 1, n);
	for (int i = 0; i < m; i++) {
	int u, v, cap;
	cin >> u >> v >> cap;
	mf.add_edge(u, v, cap);
	mf.add_edge(v, u, cap);
	}
	cout << mf.flow();
	}

view raw 15892.cpp hosted with ❤ by GitHub

질문 및 피드백 환영합니다.