问题分析

题目要求我们最小化完成所有出租车行程所需的出租车数量。每个行程都有一个出发时间、起始地址和目的地址。出租车可以在行程之间切换，但需要满足以下条件：

1. 出租车必须在新行程的出发时间至少一分钟之前到达新行程的起始地址。
2. 行程之间的切换时间是两个地址之间的曼哈顿距离（即 (|a - c| + |b - d|)）。

解题思路

1. 数据结构设计

   • 使用结构体 TEST 存储每个行程的出发时间、起始地址和目的地址。
   • 使用二维布尔数组 map 表示两个行程之间是否可以由同一辆出租车完成。
   • 使用数组 link 和 use 实现匈牙利算法，用于求解最大匹配。

2. 时间转换

   • 将时间从 hh:mm 格式转换为分钟数，方便计算。

3. 可行性判断

   • 对于每对行程 (i) 和 (j)，判断出租车是否可以在行程 (i) 结束后及时到达行程 (j) 的起始地址。具体判断条件是： [ \text{time_i} + |a_i - c_i| + |b_i - d_i| + |c_i - a_j| + |d_i - b_j| < \text{time_j} ]
   • 如果满足条件，则在 map 中标记为 true。

4. 匈牙利算法

   • 使用匈牙利算法求解最大匹配。最大匹配的数量表示可以由同一辆出租车完成的行程对数量。
   • 最终结果为 (n - \text{最大匹配数})，即最少需要的出租车数量。

代码实现

#include <iostream>
#include <cstring>  // 用于 memset
#include <cstdlib>  // 用于 abs
#include <cstdio>   // 用于 scanf 和 printf
using namespace std;

#define MAXV 505
typedef struct {
    int ti; // 行程的出发时间（以分钟为单位）
    int a, b, c, d; // 起始地址 (a, b) 和目的地址 (c, d)
} TEST;

TEST t[MAXV]; // 存储所有行程
bool map[MAXV][MAXV]; // 表示两个行程之间是否可以由同一辆出租车完成
bool use[MAXV]; // 用于匈牙利算法的标记数组
int n, link[MAXV]; // n 表示行程数量，link 用于存储最大匹配的结果

// 深度优先搜索函数，用于匈牙利算法
int dfs(int cap) {
    int i, j;
    for (i = 0; i < n; i++) { // 遍历所有行程
        if (map[cap][i] && !use[i]) { // 如果当前行程可以与第 i 个行程匹配且第 i 个行程未被访问
            use[i] = 1; // 标记第 i 个行程已访问
            j = link[i]; // 获取第 i 个行程当前匹配的行程编号
            link[i] = cap; // 尝试将第 i 个行程与当前行程 cap 匹配
            if (j == -1 || dfs(j)) { // 如果第 i 个行程未匹配，或者递归地为 j 找到新的匹配
                return true; // 匹配成功
            }
            link[i] = j; // 如果匹配失败，恢复之前的匹配
        }
    }
    return false; // 当前行程无法匹配
}

// 匈牙利算法函数，用于求解最大匹配
int hungary() {
    int i, num = 0; // num 用于记录匹配的数量
    memset(link, -1, sizeof(link)); // 初始化 link 数组，-1 表示未匹配
    for (i = 0; i < n; i++) { // 遍历所有行程
        memset(use, 0, sizeof(use)); // 每次尝试匹配前清空 use 数组
        if (dfs(i)) num++; // 如果当前行程可以匹配，匹配数量加 1
    }
    return n - num; // 最少需要的出租车数量 = 总行程数 - 最大匹配数
}

// 判断两个行程是否可以由同一辆出租车完成
bool pd(int x, int y) {
    if (x == y) return 0; // 同一行程不能匹配
    // 计算行程 x 的总时间：出发时间 + 行程 x 的行驶时间 + 从行程 x 的终点到行程 y 的起点的时间
    int tmp = abs(t[x].a - t[x].c) + abs(t[x].b - t[x].d) + t[x].ti; // 行程 x 的行驶时间
    tmp += abs(t[x].c - t[y].a) + abs(t[x].d - t[y].b); // 从行程 x 的终点到行程 y 的起点的时间
    if (tmp < t[y].ti) return 1; // 如果总时间小于行程 y 的出发时间，可以匹配
    return 0;
}

int main() {
    int i, j, h, m; // 临时变量
    int Case; // 测试用例数量
    scanf("%d", &Case); // 输入测试用例数量
    while (Case--) { // 遍历每个测试用例
        scanf("%d", &n); // 输入当前测试用例的行程数量
        for (i = 0; i < n; i++) { // 输入每个行程的详细信息
            scanf("%d:%d", &h, &m); // 输入出发时间
            t[i].ti = h * 60 + m; // 将出发时间转换为分钟
            scanf("%d %d %d %d", &t[i].a, &t[i].b, &t[i].c, &t[i].d); // 输入起始地址和目的地址
        }

        // 构建图，判断哪些行程可以由同一辆出租车完成
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++)
                map[i][j] = pd(i, j); // 调用 pd 函数判断
        }

        // 输出最少需要的出租车数量
        printf("%d\n", hungary());
    }
    return 0;
}