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

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

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

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