서론

이 글은 독자가 MCMF와 Dinic’s Algorithm을 알고 있다고 간주하고 설명합니다.
Min Cost Max Flow(MCMF) 문제를 해결하는 방법은 잘 알려져 있습니다.
이 글에서는 이 MCMF를 구하는 알고리즘에서 수행하는 몇 가지 비효율적인 작업 최적화하는 방법을 다룹니다.

문제 링크

• http://icpc.me/16002

서론

알고리즘 문제를 풀 때 랜덤을 사용해 문제를 해결하는 경우가 있습니다.
최악의 시간 복잡도와 평균 시간 복잡도가 많이 차이나는 알고리즘을 사용하는 경우에 최악의 상황을 피할 때 사용하기도 하고, 무작위 선택을 여러 번 시도하는 것으로 틀릴 확률을 줄이는 용도로 사용하기도 합니다.
이 글에서는 랜덤을 이용해 여러가지 문제를 통해 문제 풀이에 랜덤을 적용하는 방법을 다룹니다.

문제 링크

• http://icpc.me/5257

문제 링크

• http://icpc.me/16124

문제 링크

• http://icpc.me/18798

문제 링크

• http://icpc.me/10066

문제 링크

• http://icpc.me/8235

문제 링크

• http://icpc.me/16910

문제 링크

• http://icpc.me/12008