kalmiaa   8년 전

안녕하세요.

min값을 찾는 방법을 몰라 질문 드립니다.

일단 제가 푼 방식은

1. 색깔이 안맞는 node를 모두 찾는다(흰색 -> 검은색 vs 검은색 -> 흰색)

(문제 정의에 의해 위 2쌍의 개수는 같겠죠.)

2. 각 쌍을 서로 맞바꾸는데 필요한 거리를 모두 센다.

(저는 플로이드로)

3. 필요한 거리가 min값이 나오는 최소매칭을 찾는다.


이거 NP 문제 아닌가요?;;

다른분들 어떻게 푸셨는지 모르겠네요.


쌍은 최대 250개 나올 수 있을거고,

혹시나해서 bruteforce로 풀었더니 그냥 timeout 나네요...

to352   7년 전

전 플로이드 후  mcmf로 풀었습니다

kalmiaa   7년 전

제 코딩에 문제가 있나보네요.

플로이드 후 mcmf중에서도 빠르다는 헝가리안 썼는데도 타임아웃나네요 ㅠ

댓글을 작성하려면 로그인해야 합니다.