kks227   2달 전

디닉으로 풀었는데 시간초과는커녕 놀랍게도 0%에서 틀립니다.


소스(S), 싱크(E)가 있고,

소스에서는 각 단위시간(k~k+1초)에 대해 m의 용량을 가진 간선을 연결합니다.

이는 직원 수가 m명이니까 정수 단위 시간마다 최대 m명의 직원들이 다른 가구를 만들 수 있다는 겁니다.

그리고 i번 가구 정점은 wi의 용량을 가진 간선을 싱크와 잇습니다.

그리고 i번 가구를 만들 수 있는 시간대 si~di에 속하는 단위시간 정점들에서 이 가구로 갈 수 있도록 용량 1의 간선을 잇습니다.

이는 한 가구는 동시에 1명만 작업할 수 있기 때문입니다.


이렇게 단위시간마다 가구들에 1인분의 일을 유량으로 분배하여,

각 가구들마다 wi만큼의 일을 해낼 수 있으면 가능하다. 아니면 불가능하다고 결론짓고

만약 가능할 경우 유량 그래프를 보고 정답을 출력했는데... 신나게 틀립니다. 어디가 문제일까요?

디닉 알고리즘은 다른 문제에서 accept을 받은 것을 그대로 사용한 것이라 아마 문제가 없을 것이고,

그래프 구축하는 부분이나 정답 출력하는 부분에서 뭔가 잘못되었을 확률이 높다고 추측하고 있습니다. 아니면...초기화...?

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