[알고스팟] MATCHFIX - 승부조작 (C++, 최대 유량)

문제

 

https://algospot.com/judge/problem/read/MATCHFIX

algospot.com :: MATCHFIX

 

풀이

 

종만북 난이도: 중

 

이 문제를 최대 유량(네트워크 유량)으로 해결하는 방법은 다음과 같다.

이번 문제에서 유량은 승리의 횟수로 생각해 보자.

 

 

 

1. Source에서 각 결승 경기로의 간선

 

경기는 단 한 번씩만 진행할 수 있기 때문에 간선의 용량은 1로 설정해주자.

결국 모든 경기는 진행되어야 하므로 source에서 각 경기로는 1의 유량이 흐르게 된다.

 

 

2. 경기에서는 해당 경기를 진행하는 두 선수로의 간선

 

두 선수 중에 한 명만 경기에서 승리할 수 있기 때문에 결국 두 간선 중에는 한 간선에만 유량이 흐를게 될 것이다.

용량은 1로 동일하다.

(한 경기에서 두번 승리할 수는 없으므로)

 

 

 

3. 선수에서는 sink로의 간선

 

유량은 승리의 횟수를 의미하므로 선수에서 sink로의 간선에서 유량은 해당 선수가 결승 경기에서 몇 번을 승리했는지를 의미합니다.

이때 0번인 X선수가 단독 우승하기 위해서는 다른 선수들보다 총 승리 횟수가 많아야 한다.

이를 위해서 sink로의 간선의 용량을 제한해 주어야 한다.

0번 선수의 최소 승리 횟수를 K라고 하면, 나머지 1~n번 선수들의 승리 횟수는 K보다 작아야 한다.

즉, K-1 이하이어야 한다.

 

따라서 선수들의 현재 우승 횟수를 wins[i]라고 하면,

0번 선수가 최대로 더 우승할 수 있는 횟수는 K -win[0]

다른 선수들의 최대로 더 우승할 수 있는 횟수는 (K-1) - wins[i]가 된다.

 

이를 그대로 선수에서 sink로의 간선 용량으로 해주면 최대 우승 횟수 이하고 승리(유량)를 제한할 수 있다.

 

 

하지만 문제는 최소 승리 횟수 K 구하는 법이다.

 

단순히 생각하면 K의 최솟값에서 최댓값을 모두 적용해보면서 최대 유량 알고리즘을 돌릴 수도 있다.

K의 최솟값: 현재 0번 선수의 승리 횟수

K의 최댓값: 0번 선수의 경기 횟수 + 현재 0번 선수의 승리 횟수 

(0번이 모든 경기에서 승리한 경우를 의미한다.)

 

해당 K값이 정답이 되기 위해서는 모든 경기가 진행되어야만 한다.
따라서 source에서 모든 경기로 1의 유량이 흘러 최종적으로 sink에 도달해야 한다.

이때의 최대 유량은 경기의 수(match_num)와 같을 것이다.

 

하지만 모든 K에서 새로운 유량을 다시 처음부터 계산한다면, 비효율적이다.

그 이유는 K를 +1씩 증가시키며 최대 유량을 구할 때마다 결국에는 기존의 유량에 새로운 유량이 1 추가되는 것뿐이기 때문이다.

따라서 최적화를 위해 유량은 기존 그대로 사용하되, K를 증가시키며 선수에서 sink로의 간선의 용량을 업데이트 해주자.

 

 

int WinWith(int max_win){
  capacity[2+match_num][1] = max_win - wins[0];
 
  for(int i=1; i<player_num ; ++i){
    capacity[2+match_num+i][1] = (max_win - 1) - wins[i];
 
    //다른 선수의 승리 횟수가 max_win보다 큰 경우
    if(capacity[2+match_num+i][1] < 0)  
      return -1;
  }
 
  return MaximumFlow(0, 1);
}
 
int Solve(int lower, int upper){
  int ret = -1;
  int remain_flow = match_num;
  for(int max_win = lower; max_win<=upper  ; ++max_win){
    int new_flow = WinWith(max_win);
    if(new_flow == -1)
      continue;
 
    remain_flow -= new_flow;
    if(remain_flow == 0)
      return max_win;
  }
  return ret;
}

 

 

 

 

 

코드