문제 https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 정점 분할 테크닉을 통해 풀어야 하는 최대 유량 문제. 최대 유량에 대해서 잘 모른다면 다음 게시글을 참조하자. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다. 이때 간선을 정점처럼 취급하기 위해 정점을 두개의 정점..