RUN Programming Contest의 어린이 문제에서 "같은 edge를 두 번 사용하지 않는다." 는 조건을 "같은 vertex를 두 번 사용하지 않는다." 로 바꾼 문제입니다.
"같은 edge를 두 번 사용하지 않는다."는 조건은 maximum flow에서 edge의 capacity를 1로 만드는 방법으로 쉽게 해결할 수 있지만, vertex를 한 번 사용하기 위해서는 어떻게 해야 할까요?
위 질문에 대해 아래 답을 보시기 전에 UVA의 crime wave(http://acm.uva.es/p/v5/563.html)와 같은 문제를 풀어보시기 바랍니다.
[spoiler="풀이 보기"]먼저 위 질문의 답은 vertex를 쪼개서 그 사이를 capacity가 1이고, cost가 0인 edge로 연결해준다. 입니다.
예를 들어 다음과 같은 그래프가 있다고 할 때,
이를 다음과 같이 변환합니다.
즉 vertex를 (자신에게 들어오는 edge들의 vertex) -> (자신에게서 나가는 edge들을 가지는 vertex) 로 변환합니다.
이 과정에서 그래프는 항상 방향그래프가 되며, 이 그래프를 이용해서 min-cost, max-flow를 돌리면 in -> out을 잇는 edge를 단 한번만 사용하기 때문에 결과적으로 모든 vertex를 최대 한 번만 사용하는 것이 됩니다.
min-cost, max-flow를 이용하는 과정에 대한 설명은 RUN Programming Contest의 어린이 문제와 동일하기 때문에 생략합니다.[/spoiler]
[사족]
이 문제를 내기로 결정한 후에 문제 설명을 어떻게 쓸 지 고민하다가 YUTAR의 전설적인 존재인 JongMan님에 대한 오마쥬의 의미를 담아서 JongMan님의 신혼 여행을 모티브로 쓰게 되었습니다. 실제로 JongMan님은 신혼 여행을 한달 반동안 유럽으로 가십니다! (과연 문제에서처럼 프라하를 들르게 될까요?)
Toivoa
RUN Programming Contest의 어린이 문제에서 "같은 edge를 두 번 사용하지 않는다." 는 조건을 "같은 vertex를 두 번 사용하지 않는다." 로 바꾼 문제입니다.
"같은 edge를 두 번 사용하지 않는다."는 조건은 maximum flow에서 edge의 capacity를 1로 만드는 방법으로 쉽게 해결할 수 있지만, vertex를 한 번 사용하기 위해서는 어떻게 해야 할까요?
위 질문에 대해 아래 답을 보시기 전에 UVA의 crime wave(http://acm.uva.es/p/v5/563.html)와 같은 문제를 풀어보시기 바랍니다.
[spoiler="풀이 보기"]먼저 위 질문의 답은 vertex를 쪼개서 그 사이를 capacity가 1이고, cost가 0인 edge로 연결해준다. 입니다.
예를 들어 다음과 같은 그래프가 있다고 할 때,
이를 다음과 같이 변환합니다.
즉 vertex를 (자신에게 들어오는 edge들의 vertex) -> (자신에게서 나가는 edge들을 가지는 vertex) 로 변환합니다.
이 과정에서 그래프는 항상 방향그래프가 되며, 이 그래프를 이용해서 min-cost, max-flow를 돌리면 in -> out을 잇는 edge를 단 한번만 사용하기 때문에 결과적으로 모든 vertex를 최대 한 번만 사용하는 것이 됩니다.
min-cost, max-flow를 이용하는 과정에 대한 설명은 RUN Programming Contest의 어린이 문제와 동일하기 때문에 생략합니다.[/spoiler]
[사족]
이 문제를 내기로 결정한 후에 문제 설명을 어떻게 쓸 지 고민하다가 YUTAR의 전설적인 존재인 JongMan님에 대한 오마쥬의 의미를 담아서 JongMan님의 신혼 여행을 모티브로 쓰게 되었습니다. 실제로 JongMan님은 신혼 여행을 한달 반동안 유럽으로 가십니다! (과연 문제에서처럼 프라하를 들르게 될까요?)
14년 전