백준 17412 도시 왕복하기 1 c++ / Dinic 알고리즘
https://www.acmicpc.net/problem/17412 도시 정보가 주어져 있을 때, 1번이 source, 2번이 sink인 그래프에서 최대 유량을 구하는 문제와 동일합니다. 1번에서 2번으로 가는 최대 경로 개수는 결국 모든 엣지의 cap이 1인 상황에서 최대 유량을 구하는 것과 동일합니다. 최대 유량을 구하는 기법 중 빠른 것으로 알려진 Dinic 알고리즘을 적용해보았습니다. Dinic 알고리즘에 대한 설명 및 구현은 아래 글들을 참고하였습니다. https://gazelle-and-cs.tistory.com/84 디니츠의 알고리즘 (Dinitz' Algorithm)지금까지 저는 제 블로그에서 최대 흐름 문제(maximum flow problem)를 많은 포스트를 통해서 다루어 왔습니다...
알고리즘/백준
2025. 3. 5. 00:53