네트워크 유량. [2316]

[1. 문제 설명]

https://www.acmicpc.net/problem/2316

---

[2. 풀이 접근]

유량 네트워크로 접근해야 한다.

• 단, 특정 도시(이하 정점) 을 여러번 지나갈 수 없다.
• 포드-풀커슨 알고리즘은 간선의 유량에 대해서 동작한다.
• 따라서, 정점을 간선처럼 만들어야 한다.
  # 이하 코드 주석 참조.

주의 할 점.

• 정점을 간선처럼 만들 때는, 연결 된 두 도시를 입력받는 시점에서 만들면 안된다.
• 모든 입력을 받고 나서, edge 를 순회하면서 확인해야 한다.
  => 원하는 형태 : {u1 -> u2} -> {v1 -> v2} 
  => 잘못된 형태 : {u1 -> u2} <- {v1 -> v2} 
                                            \
                                             > {z1 -> z2}
  #  즉, 이미 정점 u 는 사용하였는데, 정점 v 에서 u2 와 연결되고, u2->z1 간선의 잔여 용량이 있어
     u 를 사용하는 꼴이 되버릴 수 있다.

---

[3. 코드]