caffeinism7   3년 전

주말에 MCMF/네트워크플로우 관련 게시물을 보고나서부터 문제 몇가지를 계속 풀어보고 있는데, 쉬운 MCMF 문제들은 거의 대부분의 알고리즘이 바뀌지 않고 input을 어떻게 그래프로 구성하느냐에 따라 달라지는 것 같은데 문제를 보고 딱 MCMF다! 라는 감이 오시나요? 어떤 문제들은 '나를 MCMF로 풀어라'라고 외치는것 같이 전형적인 모양이지만 또 어떤 문제들은 저같은 초보자한테는 생각하기 어려운 모양으로 그래프를 구성하고는 하더군요. 이 문제가 MCMF로 풀이가 가능할것이라는 걸 추측 가능한 팁이 있을까요?

koosaga   3년 전

의 경우에는, 입력 제한이 작고 DP로 못 풀겠으면 일단 플로우라고 지르고 봅니다. 실제로 어려운데 DP가 안되면 보통 플로우긴 하더라고요. 그래프 구성을 어떻게 하는지에 대한 힌트는 못 되지만..

매칭이나 vertex covfer, path cover 등과 연관이 있어도 플로우일 가능성이 높습니다.

MCMF냐 maxflow냐를 구분하는 건 별 의미가 없어 보입니다..

caffeinism7   3년 전

그렇군요. vertex cover와 path cover 관련 문제들도 풀어봐야겠네요.

댓글을 작성하려면 로그인해야 합니다.