shjgkwo   1년 전

어떤 시간에 제작하는 가구의 종류를 나타낸 벡터를 p[501] 라고 하겠습니다.

(xi, wi, yi) 이면 xi ~ (yi - 1) 까지 그 가구번호를 추가하는 명령을 n개의 가구를 모두 수행합니다.

이때 p[i].size() > m 일 때, i에 제거할 수 있는 가능한 1의 가중치를 두어 후보를 올려둡니다.

이때의 모습이 이분그래프가 되는데 제거 가능한 가구 후보에서 임시적으로 만들어둔 M노드로 향하는 가중치 값을

(yi - xi) - wi 라고 할때, Max Flow 로 해결하면 가능할듯 한데, 의견좀 주세요 ㅠㅠ

appa   1년 전

flow 맞아요

shjgkwo   1년 전

시간초과가 안사라져요 ㅠㅠ

MCMF는 익숙하지가 않아서 DFS로 짰는데 말이죠 ㅠㅠㅠㅠㅠ

shjgkwo   1년 전

maxflow의 시간초과를 줄이는 테크닉을 좀 가르쳐 주실수 있으신가요..

appa   1년 전

우선, MCMF는 유량에 가중치가 들어간 개념인데, 작성하신 코드는 그냥 maximum flow입니다.

풀이가 저와 달라서 뭐라 말씀드리기가 난감한데... 유량이 있는 플로우를 더 빨리 돌리고 싶으시면 dinic algorithm을 추천드립니다.

shjgkwo   1년 전

찾아보겠습니다.

감사합니다 ㅎㅎ

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