Class 71 [백준 11375] 열혈강호 [Python] 풀이 두 그룹이 있을 때, 모든 간선이 가중치가 1이고 다른 그룹으로만 향하는 그래프를 Bipartite Graph 라고 한다. 이 때, 간선을 통해 다른 정점을 점유한 상태를 matching한다고 하며 Bipartite Graph에 대한 matching을 Bipartite Matching이라고 한다. 즉, 간선의 가중치가 전부 1인 Bipartitle Graph에서 maximun flow을 구해주는 문제는 maximun matching을 구해주는 문제와 동일하다. 때문에 간단하게 DFS를 이용해 O(VE), O((N+M)E) 안에 구현하는 방법을 사용할 수 있다. 최종적으로 연결된 정점을 기록할 match 배열과, 바로 매칭이 되지 않은 경우(다른 정점과 이미 매칭된 경우) 현재 정점을 최종적으로 매칭.. 2023. 6. 14. 이전 1 다음
