백준 17412

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

 

 

최대 유량을 구하는 문제입니다. 

1번 마을에서 2번 마을로 갈 때 최대 개수를 출력하는 것이 목표입니다.

 

이때 중요한건 양방향이 아니라 단방향이기 때문에 이점을 주의해서 작성을 하였습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> v[401];
int d[401], c[401][401], f[401][401];
int result;
void max_flow(int start, int end) {
	while (1) {
		fill(d, d + 401, -1);
		queue<int> q;
		q.push(start);
		d[start] = 0;
		while (!q.empty()) {
			int x = q.front();
			q.pop();

			for (int i = 0; i < v[x].size(); i++) {
				int y = v[x][i];
				if (d[y] == -1 && c[x][y] - f[x][y] > 0) {
					q.push(y);
					d[y] = x;
					if (y == end) break;
					}
				}
			}
			if (d[end] == -1) break;
			int flow = 1000000000;
			for (int i = end; i != start; i = d[i]) {
				flow = min(flow, c[d[i]][i] - f[d[i]][i]);
			}
			for (int i = end; i != start; i = d[i]) {
				f[d[i]][i] += flow;
				f[i][d[i]] -= flow;
			}
			result += flow;
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N, P, X , Y;
	cin >> N >> P;

	for (int i = 0; i < P; i++) {
		cin >> X >> Y;
		v[X].push_back(Y);
		v[Y].push_back(X);
		c[X][Y] = 1;
	}

	max_flow(1, 2);
	cout << result;
	return 0;
}

​