시간을 가늠하기가 쉽진 않지만, map을 쓰면 lg M 인자가 더 붙으니까 248 ms로 통과하는 솔루션이라면 lg M ~ 9-10 정도 factor가 더 붙으면 아슬아슬하게 시간 초과가 날 것도 같네요. unordered_map을 쓰면 될 지도 모르지만, unordered_map은 또 자체의 오버헤드가 있어서 꼭 map보다 빠른 건 아니더라고요.
외국 사이트에서 본 기법 중에 map 대신 서로 상보적인 간선을 e, e+1 (e는 짝수)로 명명하고 e의 상대간선은 e XOR 1로 써서 O(N^2) 크기의 배열 구성을 피하는 기법이 있는데, 참고가 되셨으면 합니다.
nuclear852 3년 전
11408 열혈강호 5를 풀 떄 3640 제독 문제와 똑같은 mcmf 알고리즘이라 생각하고 비슷하게 구현하였습니다만 시간 초과가 발생하였습니다.
이 때, flow, capacity, distance를 구현할때
map<pair<int, int>, int> flow 와 같이 구현했는데,
3640번 문제에서는 시간 초과 문제 없이 통과하였지만 11408에서는 통과하지 못해 질문드립니다.
map의 사용이 배열의 사용보다 시간 차이가 얼마나 심한지, 또한 mcmf에서 map을 사용가능한 현실적인 조건이 궁금합니다.