최대유량 썸네일형 리스트형 BOJ 1031 스타대결 https://www.acmicpc.net/problem/1031 1031번: 스타 대결 첫째 줄에 지민이의 팀의 팀원 수 N과 한수의 팀의 팀원 수 M이 주어진다. 둘째 줄에는 지민이의 팀의 각 팀원이 해야 하는 경기의 수가 주어지고, 셋째 줄에는 한수의 팀의 각 팀원이 해야 하 www.acmicpc.net 우선 규칙 1~3을 만족하는 대진을 만드는 것은 최대 유량(max flow)을 이용하여 푸는 해법을 생각할 수 있다. 지민이의 팀을 왼쪽에, 한수의 팀을 오른쪽에 이분매칭 하듯이 배열한다. 지민이 팀 집합을 L, 한수팀 집합을 R이라고 하자. 양 팀 간 모든 쌍에 대해, 다시 말해 모든 L의 정점에서 R의 모든 정점으로 capacity 1의 간선을 추가한다. 최대 유량 그래프의 소스 정점에서 L의 .. 더보기 이전 1 다음