BOJ 1031 스타대결

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

1031번: 스타 대결

우선 규칙 1~3을 만족하는 대진을 만드는 것은 최대 유량(max flow)을 이용하여 푸는 해법을 생각할 수 있다.

지민이의 팀을 왼쪽에, 한수의 팀을 오른쪽에 이분매칭 하듯이 배열한다. 지민이 팀 집합을  L, 한수팀 집합을 R이라고 하자. 양 팀 간 모든 쌍에 대해, 다시 말해 모든 L의 정점에서 R의 모든 정점으로 capacity 1의 간선을 추가한다. 최대 유량 그래프의 소스 정점에서 L의 모든 정점으로 간선을 추가한다. 각 선수의 경기수가 간선의 capacity가 된다. R의 모든 정점으로 sink로 간선을 추가한다. 마찬가지로 각 선수의 경기수가 간선의 capacity가 된다. 이제 최대 유량을 흘러 보내면 대진을 만들 수 있다.

가능한 대진 중 사전순으로 가장 앞서는 대진을 구하는 것이 조금 어렵다. 최대 유량 알고리즘을 손봐서 사전 순으로 앞서는 간선에 유량을 추가하도록 고려해 보아도 코너 케이스가 너무 많다. 최대 유량 알고리즘을 직접 수정하는 방법은 안된다고 판단했다.

AC를 받은 해법은 이렇다.

우선 최대유량을 찾는다. 사전 순으로 가장 앞선 매치를 찾는다. 지민이 팀의 선수 A와 한수팀의 선수 B가 경기를 갖는다고 하자. 지금 대진에 그 매치가 포함되어 있는 경우 (최대 유량에서 해당 간선의 flow가 1) 이 매치 대신 다른 매치로 대체가 가능한지 본다.  A와 B가 플레이할 수 있는 경기수에 각각 1을 더하고, 유량을 늘릴 수 있는지 본다. 만약 유량을 늘릴 수 있다면, 바뀐 대진을 채택하고, A와 B의 경기를 취소한다. 그리고 A와 B가 플레이 가능한 경기수를 원래 상태로 되돌린다. 이제 새로운 대진은 원래 대진보다 사전 순으로 뒤에 있다.

계속해서 사전순으로 다음으로 가장 앞선 매치를 찾아 같은 과정을 반복한다. 유량을 늘리는 과정에서 사전 순으로 앞선 매치가 선택되는 것을 방지하기 위해, 한 스텝이 종료되면 두 선수의 매치를 나타내는 간선의 capacity를 0으로 만든다.