재밌는 문제 공유합니다. (백준 11377 열혈강호 3)

https://www.acmicpc.net/problem/11377

열혈강호 3

열혈강호 시리즈는 사실 너무 유명한 플로우 / 이분매칭계 웰노운이지만

이 문제가 재밌는 이유는 바로

Flow 문제를 푸는 두가지 방법

Edmonds-Karp 종류의 bfs를 적용해서 풀어도 풀리고

Bipartite matching 계열의 dfs 를 적용해도 풀린다는 점인데,

빨간 선 왼쪽의 방법을 써서

일꾼들에게 분신술을 써서 짝홀로 나눈 뒤, 짝수 놈들에게 먼저 일을 배정한 후 그 후에 홀수 놈들에게 최대 K만큼만 배정하는 방법을 사용할 수도 있고,

빨간 선 오른 쪽의 방법을 써서
K 노드를 추가하여 시작노드 S에서 K까지 k만큼만 흐르는 유량을 보낸 뒤 K를 모든 일꾼들과 연결해서
Edmonds-Karp 를 사용하는 방법도 쓸 수 있읍니다.

원래 Bipartite matching 문제들은 플로우 문제로 reducible 한 건 당연하지만,
실전 코딩에서는 이렇게 비슷한 것 같으면서도 다른 기법을 써서 문제를 풀 수 있다는 것이 매우 흥미롭읍니다.

그래서 저 두 방법 중 뭐가 더 빠를까 싶어서 다른 사람들의 코드를 보면서 속도를 비교해보니,

아뿔싸, 랭커들은 이미 더 빠른 시간복잡도를 가지고 있는 Dinic 의 알고리즘을 써서 통과해버렸네요.

Dinic의 코드를 보니 머리가 어질어질합니다.

이만 물러가겠읍니다.

다들 해피코딩

1 Like

입력값 두번째 줄설명이 뭔소린지 도저히 모르겠네요. N이랑 i랑 예제 인풋이랑 절대 이해안가네요. 이런걸 이해하고 풀이까지… 좀 쩌는군요.

image

1 Like

역시 디닉이야… 성능 확실하구만

1 Like

저도 첨에 봤을땐 당황했는데
알고보면 어려운 거 아니고 그냥 학부 알고리즘 시간에 그래프 배울때 잠깐 배우고 대충 지나가는 이분 매칭 문제 가지고
약간만 꼬아둔 거라서 이분매칭 잠깐 찾아보시면 바로 이해하실 거 같아요~

아니 … 저 빨간 부분이 이해가 안가요. 뭔소린지, 전 안될듯요 ㅋㅋㅋㅋ

1 Like

5 5 1 <- 5명의 직원과 5개의 업무가 있고, 1명의 직원은 일을 2개 할 수 있다.

3 1 2 3 <- 1번째 직원은 3가지 일을 할 수 있으며, 그 일은 1, 2, 3번째 일이다.
3 1 2 3 <- 2번째 직원은 3가지 일을 할 수 있으며, 그 일은 1, 2, 3번째 일이다.
1 5 <- 3번째 직원은 1가지 일을 할 수 있으며, 그 일은 5번째 일이다.

모든 직원에 대하여…

1 5 <- 5번째 직원은 1가지 일을 할 수 있으며 그 일은 5번째 일이다.

입니다!

1 Like

image

1 Like

모르는 사람이 보면 꼭 NP같네요

1 Like

예제만 보면, 일 5개고 각 직원마다 할수 있는 일의 순번이 정해져 있으니, 없는 순번 (4) 가 답인게… 아싸리 걍 루프띡 돌고 없는 번호 찍어내면 되지 않나 싶은데, 아니면 유니크한 순번개수(4)도… ㅋㅋㅋㅋㅋ
이런 잔머리론 어림도 없겠죠 ㅋㅋㅋㅋ

1 Like