题目链接: https://vjudge.net/contest/538552#problem/L

题意

对于 t 个测试样例，每个样例给出 n 个客人的出发时间，出发地坐标 (sx,sy) 和目的地坐标 (tx, ty)，在出发地和目的地之间一趟单程需要 |tx-sx|+|ty-sy| 分钟时间。

求每个测试样例最少需要多少辆的士才能把所有客人接完。

(0 < n < 500)

思路

对于两个客人 i, j，如果的士在接完客人 i 之后能及时赶到 j 的出发点，我们就给 i 连上一条到 j 的边。

然后这个题就变成了求最小链覆盖的问题了。然后我们就可以用一个匈牙利把这个链的数量求出来。

复杂度: O(n^3)

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>

#define orep(i,l,r) for(int i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 5e2+5;
struct st { int t, sx, sy, tx, ty; } taxi[maxN];
int vis[maxN];
std::vector<int> e[maxN];
int n, match[maxN];

inline bool dfs(int x, int color) {
  if (color == vis[x]) { return 0; }
  vis[x] = color;
  orep(it, 0, e[x].size()) {
    const int i = e[x][it];
    if (!~match[i] || dfs(match[i], color)) { match[i] = x; return 1; }
  }
  return 0;
}

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  int tc; std::cin >> tc;
  while(tc--) {
    orep(i, 0, n) { e[i].clear(); }
    memset(match, -1, sizeof(match));
    memset(vis, -1, sizeof(vis));
    std::cin >> n;
    orep(i, 0, n) {
      char c;
      int hh, mm, sx, sy, tx, ty;
      std::cin >> hh >> c >> mm >> sx >> sy >> tx >> ty;
      const int t = hh * 60 + mm;
      taxi[i].t = t;
      taxi[i].sx = sx; taxi[i].sy = sy;
      taxi[i].tx = tx; taxi[i].ty = ty;
    }
    orep(i, 0, n) {
      orep(j, 0, n) {
        if (i == j) { continue; }
        int ti = abs(taxi[i].ty - taxi[i].sy) + abs(taxi[i].tx - taxi[i].sx);
        int tj = abs(taxi[i].ty - taxi[j].sy) + abs(taxi[i].tx - taxi[j].sx);
        if (taxi[i].t + ti + tj < taxi[j].t) { e[i].push_back(j); }
      }
    }
    int ret = n;
    orep(i, 0, n) {
      ret -= dfs(i, i);
    }
    std::cout << ret; NL;
  }

  return 0;
}