https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 풀이 라이님 블로그를 참고했습니다. 점을 한 번만 표현하기 위해, '정점 분할'을 해줍니다: 점 U를 점 U, U'으로 나누어, 점 U와 U' 사이 유량이 1인 단방향 간선으로 연결합니다. 점 U에서 점 V로 가는 양방향 간선을 다음과 같이 표현합니다: U'->V 단방향 간선, V'->U 단방향 간선 이후 에드몬드-카프 알고리즘을 수행하면 됩니다. 코드 1 2 3 4 5 6 7 8 9 ..
