복습용 블로그

최대 유량 문제 : 그래프에서 가능한 최대 유량을 구하는 문제이분 매칭 문제 : bipartite graph에서 매칭 개수를 최대로 정하는 문제 MCMF : 각 엣지 별 비용이 있을 때, 최대 유량을 만족하는 최소 비용을 구하는 문제 할당 문제 : bipartite graph에서 매칭하고, 각 엣지 별 비용이 있을 때, 최대 매칭 시 최소 비용을 구하는 문제 (주로 1대1 대응 관계로 perfect matching 시 최소 비용을 계산)  즉, 이분 매칭은 최대 유량에서 모든 엣지의 cap이 1인 case, 할당 문제는 MCMF에서 모든 cap이 1인 case를 의미한다. (단 bipartite graph는 만족해야 함)  최대 유량 문제 계산 기법 1. Ford-Fulkerson : 최대 유량을 계산하..