BOJ 2316 도시 왕복하기 2

 

문제 링크 : https://www.acmicpc.net/problem/2316

2316번: 도시 왕복하기 2

 

 

정점을 한 번만 사용할 수 있다. <=> 정점을 입력 정점과 출력 정점으로 분리하고 둘 사이의 capacity=1 로 둔다.

정점 u 로 들어온 flow 는 u 의 출력 정점인 u+n 까지 기껏해야 1 의 용량을 가지는 간선을 이용하게 된다.

즉, 최대 한 번 이용할 수 있다는 뜻이다.

 

문제에서 간선 입력 u, v 는 u+n 에서 v 로 그리고 역간선은 v+n, u 로 연결하면 된다.  

 

max flow 문제가 흔히 그렇듯이 모델링을 어떻게 하느냐를 제외하면 나머지 코드는 template 이므로 특기할 사항이 없다.

 

 

어차피 각 정점의 내부 입력, 출력 정점 사이의 용량이 1 이니, 다른 정점들 사이의 용량은 민감하지 않다.

(충분히 크게 잡아도 문제가 없다.)