Skip to content

Latest commit

 

History

History
9 lines (5 loc) · 1.76 KB

solution.md

File metadata and controls

9 lines (5 loc) · 1.76 KB

MCMF 그래프를 모델링해서 문제를 해결할 수 있다. 승자 정점 N개와 패자 정점 N개, 소스, 싱크 정점을 만든다. 만약 i번 승자 정점에서 j번 패자 정점으로 유량이 흐르면 i번 참가자가 j번 참가자와 대결을 해서 i번 참가자가 이겼다는 의미로 생각하기로 하자.

먼저 소스에서 승자 정점들로 용량이 L_i-1이고 코스트가 –H_i인 간선들을 연결해 준다. 단, 우승자에게는 용량이 L_i인 간선을 연결해주어야 한다. 우승자는 이기는 경기만 하기 때문에 최대 L_i번의 이기는 경기를 하지만, 나머지 참가자들은 한 번의 지는 경기가 있기 때문에 최대 L_i-1번의 이기는 경기를 할 수 있기 때문이다. 코스트를 –H_i로 하는 것은 각 참가자들이 이기는 경기를 할 때 쌓이는 피로도를 고려하도록 한 것이다.

그 다음엔 승자 정점들에서 패자 정점들로 간선을 연결해 준다. 실력이 낮은 참가자가 높은 참가자를 상대로 이기는 경기를 할 수는 없기 때문에, A_i > A_j를 만족하는 모든 (i, j) 쌍에 대해 용량은 1이고 코스트가 A_i ^ A_j인 간선을 연결해 준다. 만약 이 간선에 용량이 흐른다는 것은 아까 언급했듯 i번 참가자가 j번 참가자를 이겼다는 의미이다. 코스트가 A_i ^ A_j이기 때문에 경기의 흥미로움이 고려된다.

마지막으로 패자 정점들에서 싱크로 용량이 1이고 코스트가 –H_i인 간선들을 연결해 준다. 코스트는 각 참가자들이 지는 경기를 할 때 쌓이는 피로도를 고려하도록 한 것이다.

이제 모든 간선의 코스트를 뒤집은 뒤 MCMF를 돌려 나온 값에 –1을 곱해 출력하면 답이 된다.