在图表中寻找完美匹配

Question

我有这个问题：

航空公司有N架不同的飞机和T名飞行员。每个飞行员都有一份他可以驾驶的飞机清单。每个航班需要 2 名飞行员。该公司希望同时运营尽可能多的航班。找到一种算法来确定是否可以同时拥有所有航班。

这是我想到的解决方案是在此图上找到最大流量：

我只是不确定容量应该是多少。你能帮我吗？

Answer 1

找到最大流量的好主意。

• 对于来自源 --> 飞行员的每个边，分配容量 1。每个飞行员一次只能驾驶一架飞机，因为他们同时运行。
• 对于从飞行员 --> 飞机的每条边，分配容量 1。如果该边充满流量 1，则表示给定飞行员正在驾驶该飞机。
• 对于从平面 --> 接收器开始的每个边，分配容量 2。这表示每个平面必须恰好由 2 个飞行员供电。

现在，找到最大流量。如果得到的最大流量是飞机数量的两倍，那么就有可能满足约束。在这种情况下，飞机和满员的飞行员之间的边代表匹配。