Việc quản lý một hãng taxi đòi hỏi sự phối hợp chặt chẽ để đảm bảo khách hàng luôn được phục vụ nhanh chóng. Một trong những thách thức lớn là tối ưu hóa việc xếp lịch cho các chuyến đi đã được đặt trước. Bài toán đặt ra là làm thế nào để thực hiện tất cả các chuyến đi đã đặt trước với số lượng xe taxi tối thiểu.

Mô hình bài toán

Để đơn giản hóa, chúng ta mô hình thành phố như một lưới hình chữ nhật. Một địa chỉ được biểu thị bằng hai số nguyên: số đường và số đại lộ. Thời gian di chuyển giữa hai địa điểm (a, b) và (c, d) được tính bằng khoảng cách Manhattan: |a - c| + |b - d| phút.

Một xe taxi có thể thực hiện một chuyến đi đã đặt trước nếu đó là chuyến đi đầu tiên trong ngày của nó, hoặc nếu nó có thể đến địa điểm đón khách của chuyến đi mới từ điểm kết thúc của chuyến đi trước đó, ít nhất một phút trước thời gian khởi hành dự kiến của chuyến đi mới. Lưu ý rằng một số chuyến đi có thể kết thúc sau nửa đêm.

Chuyển đổi bài toán sang đồ thị

Bài toán này có thể được chuyển đổi thành bài toán tìm phủ đường đi tối thiểu trên một đồ thị có hướng không chu trình (DAG). Mỗi chuyến đi đã đặt trước được xem như một đỉnh trong đồ thị.

Chúng ta sẽ tạo một cạnh có hướng từ chuyến đi i đến chuyến đi j nếu một xe taxi có thể hoàn thành chuyến đi i và sau đó tiếp tục thực hiện chuyến đi j. Điều kiện cụ thể để tạo cạnh (i, j) là:

Thời gian khởi hành chuyến i + Thời gian di chuyển của chuyến i + Thời gian di chuyển từ điểm đến của chuyến i đến điểm khởi hành của chuyến j + 1 phút <= Thời gian khởi hành chuyến j

• Thời gian di chuyển của chuyến i: Khoảng cách Manhattan từ điểm khởi hành của chuyến i đến điểm đến của chuyến i.
• Thời gian di chuyển từ điểm đến của chuyến i đến điểm khởi hành của chuyến j: Khoảng cách Manhattan từ điểm đến của chuyến i đến điểm khởi hành của chuyến j.

Vì các chuyến đi đã được sắp xếp theo thời gian khởi hành tăng dần, các cạnh trong đồ thị chỉ có thể đi từ một chuyến đi sớm hơn đến một chuyến đi muộn hơn, đảm bảo đồ thị là một DAG.

Phủ đường đi tối thiểu trên đồ thị

Một phủ đường đi của một đồ thị là một tập hợp các đường đi sao cho mỗi đỉnh trong đồ thị thuộc về ít nhất một đường đi. Phủ đường đi tối thiểu là phủ đường đi với số lượng đường đi ít nhất.

Đối với đồ thị có hướng không chu trình (DAG), định lý Dilworth phát biểu rằng số lượng đường đi tối thiểu để phủ tất cả các đỉnh bằng tổng số đỉnh trừ đi kích thước của cặp ghép cực đại trong đồ thị hai phía tương ứng.

Tức là:

Số xe taxi tối thiểu = Tổng số chuyến đi - Kích thước cặp ghép cực đại

Để áp dụng định lý này, chúng ta xây dựng một đồ thị hai phía từ đồ thị có hướng đã tạo. Mỗi đỉnh u trong đồ thị ban đầu được ánh xạ thành hai đỉnh: u_left và u_right trong đồ thị hai phía. Một cạnh từ u_left đến v_right tồn tại trong đồ thị hai phía nếu có cạnh (u, v) trong đồ thị có hướng ban đầu.

Kích thước cặp ghép cực đại trên đồ thị hai phía này sau đó sẽ được tính toán.

Giải thuật

1. Đọc dữ liệu: Đọc số lượng chuyến đi M. Với mỗi chuyến đi, đọc thời gian khởi hành (HH:MM), tọa độ điểm khởi hành (x1, y1) và tọa độ điểm đến (x2, y2). Chuyển đổi thời gian HH:MM thành số phút tính từ 00:00.
2. Xây dựng đồ thị: Khởi tạo ma trận kề doThiKe. Duyệt qua tất cả các cặp chuyến đi (i, j). Nếu chuyến đi i có thể nối tiếp chuyến đi j theo điều kiện đã nêu ở trên, đặt doThiKe[i][j] = true.
3. Tìm cặp ghép cực đại: Sử dụng thuật toán tìm cặp ghép cực đại trên đồ thị hai phía. Một phương pháp phổ biến là sử dụng DFS để tìm các đường tăng cường (augmenting paths).
   • Khởi tạo mảng ketNoiDen, trong đó ketNoiDen[v] = u nếu đỉnh u được ghép cặp với đỉnh v. Ban đầu, tất cả các phần tử được đặt là -1 (chưa được ghép).
   • Với mỗi đỉnh u (đại diện cho u_left), thực hiện một tìm kiếm DFS. Trong quá trình DFS, duy trì một mảng daThamDFS để theo dõi các đỉnh đã được thăm trong lần DFS hiện tại, tránh lặp lại chu trình.
   • Nếu tìm thấy một đường tăng cường, tăng số lượng cặp ghép lên 1.
4. Tính kết quả: Số xe taxi tối thiểu cần dùng là Tổng số chuyến đi - Số cặp ghép cực đại.

Ví dụ minh họa

Xem xét ví dụ sau:

2
2
08:00 10 11 9 16
08:07 9 16 10 11
2
08:00 10 11 9 16
08:06 9 16 10 11

Scenario 1:

• Chuyến 1: 08:00 (480 phút) từ (10,11) đến (9,16)
• Chuyến 2: 08:07 (487 phút) từ (9,16) đến (10,11)

Tính toán cho cặp (Chuyến 1, Chuyến 2):

• Thời gian di chuyển Chuyến 1: |10-9| + |11-16| = 1 + 5 = 6 phút
• Thời gian di chuyển từ điểm đến Chuyến 1 (9,16) đến điểm khởi hành Chuyến 2 (9,16): |9-9| + |16-16| = 0 + 0 = 0 phút
• Tổng thời gian cần thiết: 480 (khởi hành 1) + 6 (di chuyển 1) + 0 (di chuyển đến 2) + 1 (phút đệm) = 487 phút
• Thời gian khởi hành Chuyến 2: 487 phút

Vì 487 <= 487, có thể nối Chuyến 1 và Chuyến 2. Do đó, chỉ cần 1 xe taxi. Kết quả: 2 - 1 = 1.

Scenario 2:

• Chuyến 1: 08:00 (480 phút) từ (10,11) đến (9,16)
• Chuyến 2: 08:06 (486 phút) từ (9,16) đến (10,11)

Tính toán cho cặp (Chuyến 1, Chuyến 2):

• Tổng thời gian cần thiết (như trên): 487 phút
• Thời gian khởi hành Chuyến 2: 486 phút

Vì 487 <= 486 là SAI, không thể nối Chuyến 1 và Chuyến 2. Do đó, cần 2 xe taxi. Kết quả: 2 - 0 = 2.

Mã nguồn C++

#include <iostream>
#include <vector>
#include <string>
#include <sstream> // For parsing time (though sscanf is used here)
#include <cmath>   // For std::abs
#include <algorithm> // For std::fill

// Định nghĩa số lượng chuyến xe tối đa, dựa trên giới hạn bài toán (M < 500)
const int MAX_RIDES = 500;

// Cấu trúc dữ liệu để lưu thông tin một chuyến xe
struct ChuyenXe {
    int thoiGianKhoiHanhPhut; // Thời gian khởi hành tính bằng phút từ 00:00
    int x_di, y_di;           // Tọa độ điểm khởi hành
    int x_den, y_den;         // Tọa độ điểm đến

    // Hàm tính thời gian di chuyển của chuyến xe này
    int tinhThoiGianChuyenDi() const {
        return std::abs(x_di - x_den) + std::abs(y_di - y_den);
    }
};

// Các biến toàn cục cho ma trận kề và quá trình tìm cặp ghép (phổ biến trong lập trình thi đấu)
// doThiKe[u][v] = true nếu xe taxi có thể đi từ chuyến u sang chuyến v
bool doThiKe[MAX_RIDES][MAX_RIDES]; 
// ketNoiDen[v] = u nghĩa là chuyến v được ghép cặp với chuyến u
int ketNoiDen[MAX_RIDES];           
// daThamDFS[v] = true nghĩa là đỉnh v đã được thăm trong lần DFS hiện tại
bool daThamDFS[MAX_RIDES];          

// Hàm hỗ trợ để phân tích chuỗi thời gian "HH:MM" thành tổng số phút
int parseThoiGian(const std::string& thoiGianStr) {
    int gio, phut;
    sscanf(thoiGianStr.c_str(), "%d:%d", &gio, &phut);
    return gio * 60 + phut;
}

// Hàm DFS để tìm đường tăng cường trong đồ thị hai phía
bool timDuongTangCuong(int u, int soChuyenXe) {
    for (int v = 0; v < soChuyenXe; ++v) {
        // Nếu có cạnh từ u đến v VÀ v chưa được thăm trong lần DFS hiện tại
        if (doThiKe[u][v] && !daThamDFS[v]) {
            daThamDFS[v] = true; // Đánh dấu v đã thăm
            // Nếu v chưa được ghép cặp HOẶC có thể tìm được đường tăng cường từ đỉnh đã ghép với v
            if (ketNoiDen[v] == -1 || timDuongTangCuong(ketNoiDen[v], soChuyenXe)) {
                ketNoiDen[v] = u; // Ghép cặp u với v
                return true;      // Tìm thấy đường tăng cường
            }
        }
    }
    return false; // Không tìm thấy đường tăng cường từ u
}

// Hàm tính toán cặp ghép cực đại trên đồ thị hai phía
int tinhGhepCapCucDai(int soChuyenXe) {
    // Khởi tạo tất cả các chuyến xe đích là chưa được ghép cặp
    std::fill(ketNoiDen, ketNoiDen + soChuyenXe, -1); 
    int soGhepCap = 0; // Đếm số lượng cặp ghép
    
    // Thử tìm đường tăng cường từ mỗi chuyến xe nguồn u
    for (int u = 0; u < soChuyenXe; ++u) {
        // Đặt lại trạng thái thăm cho mỗi lần DFS mới
        std::fill(daThamDFS, daThamDFS + soChuyenXe, false); 
        if (timDuongTangCuong(u, soChuyenXe)) {
            soGhepCap++; // Nếu tìm thấy đường tăng cường, tăng số cặp ghép
        }
    }
    return soGhepCap;
}

int main() {
    // Tối ưu hóa I/O cho lập trình thi đấu
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int soLuotKiemTra; // Số lượng kịch bản kiểm tra
    std::cin >> soLuotKiemTra;
    while (soLuotKiemTra--) {
        int soChuyenXe; // Số lượng chuyến xe trong kịch bản hiện tại
        std::cin >> soChuyenXe;
        std::vector<ChuyenXe> danhSachChuyenXe(soChuyenXe); // Lưu trữ thông tin các chuyến xe

        // Đọc dữ liệu cho từng chuyến xe
        for (int i = 0; i < soChuyenXe; ++i) {
            std::string thoiGianStr;
            std::cin >> thoiGianStr;
            danhSachChuyenXe[i].thoiGianKhoiHanhPhut = parseThoiGian(thoiGianStr);
            std::cin >> danhSachChuyenXe[i].x_di >> danhSachChuyenXe[i].y_di
                     >> danhSachChuyenXe[i].x_den >> danhSachChuyenXe[i].y_den;
        }

        // Khởi tạo ma trận kề, tất cả các cạnh ban đầu là false (không có kết nối)
        for (int i = 0; i < soChuyenXe; ++i) {
            for (int j = 0; j < soChuyenXe; ++j) {
                doThiKe[i][j] = false;
            }
        }

        // Xây dựng đồ thị có hướng bằng cách xác định các cạnh
        for (int i = 0; i < soChuyenXe; ++i) {
            for (int j = 0; j < soChuyenXe; ++j) {
                if (i == j) continue; // Một xe taxi không thể thực hiện cùng một chuyến hai lần liên tiếp

                // Thời gian di chuyển của chuyến xe i
                int thoiGianDiChuyenChuyenI = danhSachChuyenXe[i].tinhThoiGianChuyenDi();
                
                // Thời gian di chuyển từ điểm kết thúc chuyến i đến điểm khởi hành chuyến j
                int thoiGianDenDiemKhoiHanhChuyenJ = std::abs(danhSachChuyenXe[i].x_den - danhSachChuyenXe[j].x_di) +
                                                  std::abs(danhSachChuyenXe[i].y_den - danhSachChuyenXe[j].y_di);

                // Điều kiện để nối chuyến i với chuyến j:
                // Xe taxi kết thúc chuyến i, sau đó di chuyển đến điểm khởi hành của chuyến j,
                // và phải đến đó ít nhất 1 phút trước thời gian khởi hành của chuyến j.
                if (danhSachChuyenXe[i].thoiGianKhoiHanhPhut + thoiGianDiChuyenChuyenI + thoiGianDenDiemKhoiHanhChuyenJ + 1 <=
                    danhSachChuyenXe[j].thoiGianKhoiHanhPhut) {
                    doThiKe[i][j] = true; // Tạo cạnh từ chuyến i đến chuyến j
                }
            }
        }

        // Tính toán số cặp ghép cực đại
        int soGhepCapCucDai = tinhGhepCapCucDai(soChuyenXe);
        
        // Kết quả là số chuyến xe - số cặp ghép cực đại
        std::cout << soChuyenXe - soGhepCapCucDai << "\n";
    }
    return 0;
}