Pan*_*pta 6 algorithm optimization data-structures
一排有 N 辆汽车，从 1 到 N 编号。一个人拍了 M 辆汽车的照片。对于每张照片，出现在其中的汽车由元组 (i, j) 给出，这意味着从第 i 辆汽车到第 j 辆汽车的所有汽车都将出现在该照片中。
请注意，所有照片不必涵盖每辆车。一辆汽车可以出现在不止一张照片中。
假设每张照片恰好包含1辆紫色汽车。找出可能的最大数量的紫色汽车。如果不可能，则打印 -1。
输入：第一行包含 N 和 M。下一行包含 M 对 (x, y)，它们表示包含从第 x 辆汽车到第 y 辆汽车的汽车的照片。输出：可能的紫色汽车的最大数量。
例子 ：
输入：
5 1
(3 5)
输出：3
说明：3到5只有一辆车可以是紫色的。为了最大化紫色汽车的数量，汽车 1 和汽车 2 将是紫色的。
输入：
5 1
(4 4)
输出：5
输入：
5 3
(1 4), (3 5), (3, 4)
输出：1
说明： 3 或 4 都可以是紫色的车。
输入：
5 2
(1, 4), (2, 5)
输出：2
说明：Car 1 和 Car 5 可以是紫色的。
输入：
10 3
(1 5), (6, 10), (1, 10)
输出：-1
说明：在这种情况下，每个区间不可能恰好有 1 辆紫色汽车。
如果我没记错的话，该问题可以作为网络问题解决，如下所示。
网络的节点集有源节点s和终端t；想象一下水槽位于最左边的位置，终端位于最右边的位置，并且水流从左向右。接下来s为每辆车放置一个节点并连接s到每辆车。在汽车节点旁边为每个间隔创建一个节点。现在从汽车节点开始，创建到 的路径t，遍历区间节点集；该路径经过包含汽车的每个区间。
除了s和 之外t，每个节点中的流量都被限制为每个区间1恰好有哪些车型1必须涂成紫色；弧不需要明确地受到约束。s最后通过一些网络流算法，最大化从到 的流强度t。将其节点具有非零流量的每辆汽车涂成紫色。如果实例不允许可行的流，则初始问题实例是不可行的。