[codeforces] 1913E. Matrix Problem

문제 링크

첫 레드 문제 솔브입니다.
2100이 solved.ac 기준으로 대략 P3 정도 되는것 같아 2400정도면 P1~D5 정도 되지 않을까 싶어 하나만 풀어보자 싶어 도전해봤는데 역시 쉽지 않네요. 그래도 어떻게든 하나 잡았으니 만족합니다...

크기가 $N \times M$이고 모든 요소가 0 또는 1인 배열 $a$가 있습니다.
저희는 배열의 요소를 하나 골라 0 또는 1로 변경하는 연산을 수행할 수 있고 해당 연산을 최소한으로 수행해서 $i$번째 행에는 $1$의 갯수가 $A_{i}$, $j$번째 열에는 $1$의 갯수가 $B_{j}$가 되도록 만들려고 합니다. $(1 \leq i \leq n, 1 \leq j \leq m)$

먼저 입력에 따라 아래 그림과 같이 비용이 있는 유량 그래프로 모델링을 합니다.

그림이 너무 복잡해서 각 간선의 용량과 비용은 아래에 설명하겠습니다.

• $source \rightarrow r_{i, 0}$ : 용량은 $N-A_{i}$, 비용은 $a_{i, j}$로 설정합니다.
• $source \rightarrow r_{i, 1}$ : 용량은 $A_{i}$, 비용은 $1-a_{i, j}$로 설정합니다.
• $r_{i, k} \rightarrow a_{i, j, k}$ : 용량은 $1$, 비용은 $0$으로 설정합니다.
• $a_{i, j, k} \rightarrow c_{j, k}$ : 용량은 $1$, 비용은 $0$으로 설정합니다.
• $c_{j, 0} \rightarrow sink$ : 용량은 $M-B_{j}$, 비용은 $0$으로 설정합니다.
• $c_{j, 1} \rightarrow sink$ : 용량은 $B_{j}$, 비용은 $0$으로 설정합니다.

위 유량 그래프에서 $source$에서 $sink$로 유량을 흘려보내면 아래와 같은 사실을 얻을 수 있습니다.

• 최대 유량이 $MN$이면 연산을 통해 지문에서 요구하는 배열을 만들 수 있습니다. 반대로 최대 유량이 $MN$보다 작으면 연산을 아무리 해도 지문에서 요구하는 배열을 만들 수 없습니다.
• 지문에서 요구하는 배열을 만들 수 있다면 최대 유량을 흘려보내는데 드는 비용이 연산의 횟수가 됩니다. 당연히 최대 유량을 흘려보낼 때 드는 비용의 최솟값이 지문에서 요구하는 배열을 만들기 위한 연산의 최소 횟수가 됩니다.

즉, MCMF 알고리즘을 사용하면 답을 얻을 수 있습니다.

시간복잡도는 $O(MNf)$입니다. 사실 spfa 알고리즘의 경우 평균 $O(E)$, 최악의 경우 $O(VE)$의 시간복잡도를 가지고 있어 최악의 경우 $O(M^2N^2f)$가 될 수도 있는게 아닌가 하고 생각해 봤습니다. 물론 그래프의 연결 구조까지 입력에 따라 수시로 바뀐다면 worst case를 저격하는게 가능할 수도 있습니다만 위 문제에서는 입력에 따라 간선의 비용(spfa에서 가중치 역할)이 바뀌지만 그래프의 간선의 연결 구조까지 바뀌지는 않습니다. 그래서 모델링한 그래프가 가중치가 어떻게 잘못 걸려서 worst case를 만들 수 있는 구조가 아니라면 괜찮을테고 이 문제에서는 그렇게 모델링이 가능해서 잘 도는것 같습니다. 물론 직접 돌려봐야 걸리는지 안 걸리는지 알 수 있을테니 만약에 돌렸는데 TLE가 난다면 다른 모델링을 생각해 봐야겠죠...