Dev_Diary

https://www.acmicpc.net/problem/11378https://dev-diary-0717.tistory.com/176기존에 포스팅한 열혈강호 3 과 같은 문제라고 볼 수 있습니다.다만 달라진 점은 한 사람이 추가로 담당할 수 있는 일이 1 개가 아닌 K 개가 된 것인데 추가 노드에서 직원 노드로 간선을 만들 때 흐를 수 있는 유체의 양을 K 로 설정하면 K 번 모두 탐색을 하며 최대치까지 부여하기 때문에 해결됩니다.import sysfrom collections import deque, defaultdictinput = sys.stdin.readlinedef solution(N, M, K, hope_list):    # 흐를수 있는 유체의 양    flowable = defaultdic..

https://www.acmicpc.net/problem/11377열혈강호 2 까지는 이분매칭으로 풀었지만 해당 문제는 네트워크 플로우 알고리즘 중 에드몬드 카프 알고리즘으로 풀었습니다.아마 2 개의 일을 할 수 있는 K명을 정하는데 큰 지장이 있을 것이라고 생각합니다.모두 두 개씩 일을 할 수 있을 때 (열혈강호 2) 이분 매칭을 두 번 돌렸던 것을 생각해 우선 모두에게 일을 하나씩 되는대로 할당하고 추가적으로 일을 할당하는 방식으로 진행했습니다. 문제에서 제시한 예제를 그래프로 만들면 이렇게 됩니다.해당 그래프에서 이동하는 경로는 0 - 1 - 6 - 120 - 2 - 7 - 120 - 3 - 10 - 120 - 11 - 1 - 8 - 12 으로 우선 모든 직원들에게 일을 할당한 뒤 추가 노드에서 일..