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

문제

N개의 도시가 P개의 단방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 가며 워해머를 한다. 성실한 이석원은 1번에서 2번으로 가는 서로 다른 경로를 최대한 많이 찾으려고 하는데, 이때 한 경로에 포함된 길이 다른 경로에 포함되면 안된다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다.

입력

첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다.

출력

1번에서 2번으로 가는 서로 다른 경로의 최대 개수를 출력한다.

 

 

1번에서 2번으로 가는 서로 다른 경로의 최대 개수를 구해야 합니다.

최대 유량 알고리즘을 사용합니다.

#include<bits/stdc++.h>

using namespace std;
typedef pair<int, int> pi;
int c[401][401], f[401][401], N, P, ans;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int from, to;
	cin >> N >> P;
	while (P--) {
		cin >> from >> to;
		c[from][to] = 1;  //단방향 간선 그래프
	}
	while (1) {  
		vector<int>parent(400, 0);
		queue<int>q;
		parent[1] = 1;
		q.push(1);
		while (!q.empty()) {//BFS 수행
			int here = q.front();
			q.pop();

			for (int there = 1; there <= N; there++) {
				if (c[here][there] - f[here][there] > 0 && !parent[there]) { 최대 유량 알고리즘
					q.push(there);
					parent[there] = here;
				}
			}
		}
		if (parent[2] == 0)break;

		for (int p = 2; p != 1; p = parent[p]) {
			f[parent[p]][p] = 1;
			f[p][parent[p]] = -1;
		}
		ans++;
	}
	cout << ans;
}