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

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

15892번: 사탕 줍는 로봇

사탕의 개수를 노드 간 연결된 간선의 용량으로 생각하면 네트워크 플로우 (최대 유량)으로 쉽게 풀 수 있음.

네트워크 플로우의 개념은 BFS로 시작->도착점 경로의 최소 유량 flow를 탐색하여 u->v 유량에 더해주고 역방향 v->u 유량에서 빼서 더이상 유량을 흘려보낼 수 없을 때 까지 반복합니다.

주의할 점은, 이 문제는 양방향이라 실수할 확률이 낮지만 단방향 그래프에서도 역간선을 고려하기 위해 a,b,cost 에 대하여 b->a의 간선 정보를 추가해야하며, 양방향이므로 a->b와 b->a의 cost를 같이 증가시켜야 합니다.

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

int n, m;
int c[301][301] = { 0, };
int f[301][301] = { 0, };
vector<int> v[301];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		c[a][b] += cost;
		c[b][a] += cost;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int ans = 0;
	while (1) {
		int prev[301];
		memset(prev, -1, sizeof(prev));
		queue<int> q;
		q.push(1);
		while (!q.empty()) {
			int node = q.front(); q.pop();
			for(auto i : v[node]){
				if (prev[i] ==-1 && c[node][i] > f[node][i]) {
					q.push(i);
					prev[i] = node;
					if (i == n) {
						break;
					}
				}
			}
		}
		if (prev[n] == -1) {
			break;
		}
		int flow = 2e6;
		for (int i = n; i != 1; i = prev[i]) {
			flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
		}
		ans += flow;
		for (int i = n; i != 1; i = prev[i]) {
			f[prev[i]][i] += flow;
			f[i][prev[i]] -= flow;
		}
	}
	cout << ans;

}