여행 계획

Question

한 국가에 대한 전체 버스 스케줄을 가지고 있다면, 하루에 지정된 두 정류장 사이를 오가며 이동할 수있는 최대 인원 수를 어떻게 알 수 있습니까?

나는 버스 정류장이 모든 버스 정류장의 출발 시간과 도착 시간의 전체 목록과 각 버스의 용량을 제공한다고 가정합니다. 질문에 시작과 끝이 주어집니다.

목적지까지 최단 시간을 제공하고이 경로를 따라 출발하는 모든 버스를 채우는 버스 순서를 결정한 다음 각 버스가 정류장에 도착하면 다음과 같이 많은 승객을 운송 할 수 있습니다. 떠나는 다음 버스까지 가능합니다. 그러나 이것이 최대 용량을 가져야하는 이유는 없습니다.

이 문제는 가장 빨리 해결할 수 있습니까? 예를 들어 M 도시의 경우 총 N 개의 레코드가 있다고 가정합니다. 경로 기록 R number는 번호 Kᵢ, 수용력 Cᵢ, Kᵢ 도시 번호 목록, Kᵢ 도착 시간 및 Kᵢ 출발 시간 목록을 포함합니다. (R first의 첫 번째 도착 시간과 마지막 출발 시간은 부적합합니다.) 폭 우선 탐색 프로그램은 O (M * N) 시간에 문제를 풀 수 있습니까?

Answer 1

이것은 이상한 퍼즐이 아닙니다. 알고리즘 질문입니다. 이를 해결하는 한 가지 방법은 모든 (위치, 도착 시간) 및 (위치, 출발 시간)마다 노드가있는 방향 그래프를 만드는 것입니다. 각 도착 노드는 이전 위치가 아닌 동일한 위치의 모든 출발점에 대해 무한대의 호를 갖습니다. 각 출발 노드는 (버스 스케줄에 따라) 버스의 용량으로 가중치 화 된 적절한 도착 노드 각각에 대한 호를가집니다. 그런 다음 좋아하는 알고리즘을 사용하여 소스에서 싱크까지 최대 플로우를 찾을 수 있습니다.

소스 노드는 시작 위치에서 시간이 0 일 때 도착 노드 여야하며 싱크 노드는 끝 위치의 종료 시간에 출발 노드 여야합니다.