题意：
有m个人要坐出租车，每个人给出出发时间，出发地点和目的地（以二维坐标表示），两个地点之间所花的时间计算方式是两点之间的哈密顿距离。现在需要排遣车出去，一辆车每次只能装一个人，如果一辆车在装完一个人A之后，再到达另一个人B的出发地点的时间，比这个人的出发时间至少提前1分钟，那么这个车就可以乘坐B。
问排遣的最少的车的数目。
思路：
直观的来看，每一辆车的路径是一个DAG，那么这个问题就转化成了DAG的最小路径覆盖。
最小路径覆盖的定义：在一个有向图中，找出最少的路径，使得途中的所有点都被覆盖，此题所求的最小路径覆盖是不相交的最小路径覆盖。
最小路径覆盖的算法是把每个点拆成起点i和终点i’，如果有一条边从i到j，那么就从i向j’连边，此时这个图就成为了一个二分图。
二分图的最小路径覆盖= 点数 – 二分图的最大匹配
然后此题就是两点之间连边的问题，时间可以换算成分钟数表示比较方便，然后当一个点的结束时间加上 结束点到另一个点的行驶时间，如果这个时间小于另一个点的出发时间，那么这两点之间就可以连边。
匈牙利算法，复杂度O(n^2)。
代码：
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std; const int N = ;
typedef pair<int,int> pii; struct node
{
int st,en; node(int a,int b)
{
st = a;
en = b;
}
}; vector<pii> ps;
vector<node> ns;
vector<int> g[N];
bool vis[N];
int link[N]; int mabs(int x)
{
return x >= ? x : -x;
} bool dfs(int u)
{
for (int i = ;i < g[u].size();i++)
{
int v = g[u][i]; if (!vis[v])
{
vis[v] = ; if (link[v] == - || dfs(link[v]))
{
link[v] = u;
link[u] = v; return true;
}
}
} return false;
} int solve(int n)
{
memset(link,-,sizeof(link)); int res = ; for (int i = ;i < n;i++)
{
if (link[i] == -)
{
memset(vis,,sizeof(vis));
if (dfs(i)) res++;
}
} return res;
} int main()
{
int t; scanf("%d",&t); while (t--)
{
int n; scanf("%d",&n); ns.clear();
ps.clear(); for (int i = ;i < n;i++)
{
g[i].clear();
} for (int i = ;i < n;i++)
{
int a,b;
int x,y,z,w; scanf("%d:%d",&a,&b);
scanf("%d%d%d%d",&x,&y,&z,&w); int st = a * + b;
int en = st + mabs(x - z) + mabs(y - w); ns.push_back(node(st,en));
ps.push_back(pii(x,y));
ps.push_back(pii(z,w));
} for (int i = ;i < n;i++)
{
for (int j = i + ;j < n;j++)
{
pii st = ps[*i + ],en = ps[*j]; int cost = mabs(st.first - en.first) + mabs(st.second - en.second); if (ns[i].en + cost < ns[j].st) g[i].push_back(n+j);
}
} int ans = solve(n); printf("%d\n",n - ans);
} return ;
}