流程/图表:最早的日期城市将被连接

Question

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

有些城市居住在同一座岛屿上，因此可以很容易地相互联系。这些城市形成了一个社区。有这样的社区。

示例输入：

由城市组成的社区：

• 切斯尼，本特利，迪伊
• Immy，Caleigh，Kinley
• Ady，Georgette，Elaina，Tanya

规划的基础设施项目：

• 2020年-04-12:宾利与金利之间的隧道
• 2021-01-04:迪伊与金利之间的桥梁
• 2021-07-01: Immy与Ady之间的隧道
• 2021-10-12:切斯尼和乔治特之间的隧道。

例如，考虑到Chesney和Georgette这两个城市，这些城市连接起来的最早日期是2021-07-01。

我想出两种方法来模拟这个问题。无论是作为一个图问题，所以它可以通过MST算法来解决，也可以通过将其简化为网络流来解决。我看到了航空公司调度问题的一些问题，这个问题可以用网络流来解决，这使我认为这个问题更可能是一个网络流问题。然而，我不太清楚如何将这个特定的问题建模为一个网络流问题。有人能引导我朝正确的方向前进吗？

Answer 1

您可以用Kruskal的算法来解决这个问题，根据完成日期而不是权重对边进行排序。