minimum cost flow 알고리즘

🔗 G - Domino Covering SUM (AtCoder Beginner Contest 407)

그래프에서 최대 유량을 찾는 알고리즘이 있다. 이 때는 그냥 찾으면 되지만, 간선에 비용이 딸려있는 경우가 있다.

각 유량에 대해 최소 비용을 찾고자할 때 minmum cost flow알고리즘을 사용한다. 앳코더 라이브러리에 잘 정리가 되어 있는데, .slope(시작, 도착)를 사용하면 \( (\text{flow, cost}) \) vector가 반환된다. 시간 복잡도는 \( \text{유량} \times (\text{정점} + \text{간선}) \) 정도이다.

 

아래 문제를 통해 이 알고리즘을 더 이해해보자.

[G - Domino Covering SUM]

---

문제 설명

세로 도미노와 가로 도미노를 사용하면 격자판을 덮을 수 있다. 각 칸에는 숫자가 쓰여져 있고, 도미노로 덮이지 않은 영역들에 적힌 숫자의 합이 점수가 된다. 최대 점수를 구하라.

 

풀이

도미노로 덮힌 영역의 최소 숫자 합을 구하면 된다. 도미노를 덮는 문제는 보통 dp, bit dp로 많이 해결하는데, 이 문제는 숫자가 크기 때문에 다른 방법으로 접근해야 한다. 각 칸을 정점으로 보고 인접한 칸을 간선으로 연결한 그래프는 이분 그래프다. 그 이유는 격자판을 체스판으로 대응시켜 검은색, 흰색 두 가지 부류로 칸을 나눌 수 있기 때문이다.

간선의 가중치를 연결된 정점에 적힌 숫자의 합으로 설정하면, 간선의 가중치 합이 최소가 되도록 매칭하는 문제로 바뀐다. 이는 minimum cost flow 알고리즘으로 풀 수 있다. 비용이 음수가 되면 안 되기 때문에 각 간선에 충분히 큰 상수를 더해준다.