Учитывая N городов и M запланированных инфраструктурных проектов, мне нужно найти подход, чтобы определить самую раннюю дату, когда два конкретных города будут соединены.
Некоторые города находятся на одном острове и поэтому могут быть легко доступны друг от друга.Эти города образуют сообщество.Есть C таких сообществ.
Пример ввода :
Сообщества, состоящие из городов:
- Чесни, Бентли, Ди
- Имми, Кейли,Kinley
- Ady, Georgette, Elaina, Tanya
Запланированные инфраструктурные проекты:
- 2020-04-12: туннель между Bently и Kinley
- 2021-01-04: Мост между Ди и Кинли
- 2021-07-01: Туннель между Имми и Ади
- 2021-10-12: Туннель между Чесни и Джорджет.
Например, учитывая города Чесни и Джорджетт, самая ранняя дата, в которую эти города связаны, - 2021-07-01.
Я думаю о двух подходах, которые можно смоделировать.Либо как проблема графа, так что она может быть решена с использованием алгоритма MST или путем сокращения ее до сетевого потока.Я вижу некоторые плюсы к проблеме планирования авиаперевозок, которые могут быть решены с использованием сетевого потока, что заставляет меня думать, что эта проблема скорее связана с сетевым потоком.Однако я не совсем уверен, как смоделировать эту конкретную проблему как проблему сетевого потока.Может ли кто-нибудь направить меня в правильном направлении?