流程/图表：将连接最早的城市

Question

给定 N 个城市和 M 个计划中的基础设施项目，我需要找到一种方法来确定连接两个特定城市的最早日期。

一些城市位于同一个岛上，因此可以很容易地从彼此到达。这些城市形成了一个社区。有 C 个这样的社区。

示例输入：

由城市组成的社区：

• 切斯尼、本特利、迪伊
• 伊米、卡利、金利
• 阿迪、乔吉特、伊莱娜、坦尼娅

计划的基础设施项目：

• 2020-04-12：本特利和金利之间的隧道
• 2021-01-04：Dee 和 Kinley 之间的桥梁
• 2021-07-01：Immy 和 Ady 之间的隧道
• 2021-10-12：Chesney 和 Georgette 之间的隧道。

例如，给定切斯尼和乔治特这两个城市，这些城市最早的连接日期是 2021-07-01。

我正在考虑可以对这个问题建模的两种方法。作为图问题，可以使用 MST 算法或将其简化为网络流来解决。我看到 Airline Scheduling 问题有些相似，可以使用网络流来解决，这让我认为这个问题更可能是网络流问题。但是我不太确定如何将这个特定问题建模为网络流问题。有人可以指导我正确的方向吗？

Answer 1

您可以使用 Kruskal 算法解决此问题，按完成日期而不是权重对边进行排序。