[백준 17412] 도시 왕복하기1

문제 링크 => 17412번: 도시 왕복하기 1 (acmicpc.net)

17412번: 도시 왕복하기 1

---

최대 유량을 이용하는 문제이다.

 

이 문제에서는 이전에 풀었던 최대 유량 문제와는 다르게 from에서 to로만 가는 단방향으로 연결되어 있다는 것이다.

 

따라서 2차원 배열 capacity를 채우는 과정은 c[from][to] = 1 만 해주면 끝이다. (from => to가 중복해서 나타나는 일이 없으므로 +는 하지 않음)

 

세팅이 끝나면 Edmond carp Algorithm 을 이용하여 풀면 끝이다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <stdio.h>
#include <iomanip>
#include <map>
#include <cstdlib>

#define MAX 401
#define INF 100000000

using namespace std;

int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> v[MAX];

void input() {
	int V, E;
	cin >> V >> E;
	
	for (int i = 0; i < E; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
		c[x][y] = 1;
	}
}

void solve(int start, int end) {
	
	int result = 0;

	while (1) {
		fill(d, d + MAX, -1);
		queue<int> Q;
		Q.push(start);

		while (!Q.empty()) {
			int from = Q.front();
			Q.pop();
			for (int to : v[from]) {
				if (d[to] == -1 && c[from][to] - f[from][to] > 0) {
					Q.push(to);
					d[to] = from;
				}
			}
		}
	
		if (d[end] == -1) break;

		int flow = INF;
		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;
	}

	cout << result << endl;
}

int main(void) {

	input();
	solve(1, 2);

	return 0;
}