11493번 - 동전 교환
안녕하세요.
min값을 찾는 방법을 몰라 질문 드립니다.
일단 제가 푼 방식은
1. 색깔이 안맞는 node를 모두 찾는다(흰색 -> 검은색 vs 검은색 -> 흰색)
(문제 정의에 의해 위 2쌍의 개수는 같겠죠.)
2. 각 쌍을 서로 맞바꾸는데 필요한 거리를 모두 센다.
(저는 플로이드로)
3. 필요한 거리가 min값이 나오는 최소매칭을 찾는다.
이거 NP 문제 아닌가요?;;
다른분들 어떻게 푸셨는지 모르겠네요.
쌍은 최대 250개 나올 수 있을거고,
혹시나해서 bruteforce로 풀었더니 그냥 timeout 나네요...
전 플로이드 후 mcmf로 풀었습니다
제 코딩에 문제가 있나보네요.
플로이드 후 mcmf중에서도 빠르다는 헝가리안 썼는데도 타임아웃나네요 ㅠ
댓글을 작성하려면 로그인해야 합니다.
kalmiaa 8년 전
안녕하세요.
min값을 찾는 방법을 몰라 질문 드립니다.
일단 제가 푼 방식은
1. 색깔이 안맞는 node를 모두 찾는다(흰색 -> 검은색 vs 검은색 -> 흰색)
(문제 정의에 의해 위 2쌍의 개수는 같겠죠.)
2. 각 쌍을 서로 맞바꾸는데 필요한 거리를 모두 센다.
(저는 플로이드로)
3. 필요한 거리가 min값이 나오는 최소매칭을 찾는다.
이거 NP 문제 아닌가요?;;
다른분들 어떻게 푸셨는지 모르겠네요.
쌍은 최대 250개 나올 수 있을거고,
혹시나해서 bruteforce로 풀었더니 그냥 timeout 나네요...