algorithm - 流/图 : Earliest date cities will be connected

Question

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

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

示例输入:

由城市组成的社区:

• 切斯尼、本特利、迪伊
• 艾米、卡利、金利
• Ady、Georgette、Elaina、Tanya

计划的基础设施项目:

• 2020-04-12:本特利和金利之间的隧道
• 2021-01-04:Dee 和 Kinley 之间的桥梁
• 2021-07-01:艾米和阿迪之间的隧道
• 2021-10-12:Chesney 和 Georgette 之间的隧道。

例如，对于 Chesney 和 Georgette 这两个城市，这些城市最早的连接日期是 2021 年 7 月 1 日。

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

Answer 1

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