大白例题P356 你在一座城市里负责一个大型活动的接待工作。你需要去送m个人从出发地到目的地，已知每个人的出发时间出发地点，和目的地点，你的任务是用尽量少的出租车送他们，使得每次出租车接客人，至少能提前一分钟达到他所在的位置，城市为网格 (x1,y1) ===>(x2,y2) 需要|x1-x2|+|y1-y2|分钟
题解：
本题的模型是DAG的最小路径覆盖。所谓最小路径覆盖就是在图中找尽量少的路径，使得每个结点恰好在一条路径上（话句话说，不同路径不能有公共点）。单独的节点也可以作为一条路径。
本题中“时间” 是一个天然的序， 因此可以构图如下： 每个客人是一个节点，如果同一个出租车在接完客人u以后来得及接客人v，离岸边u_>v， 不难发现是一个DAG, 并且它的最小 路径覆盖就是本题的答案。
大白书 P357讲解:DAG最小路径覆盖的解法把所有节点i 拆成 X 节点i 和Y 节点i' , 如果图G中存在有向边 i->j，则在二分图中引入i->j'， 设最大匹配数位m，则结果就是 n-m.
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn =;
struct person{
int time;
int sx,sy,tx,ty;
}P[maxn];
struct BPM{
int n,m;
int left[maxn],right[maxn];
bool S[maxn],T[maxn];
vector<int>G[maxn];
void init(int n, int m){
this->n = n;
this->m = m;
for(int i=; i<m; i++) G[i].clear();
}
void add_edg(int u, int v){
G[u].push_back(v);
}
bool match(int u){
S[u] =true;
for(int i =; i<(int )G[u].size(); i++){
int v = G[u][i];
if(T[v] == false){
T[v]=true;
if(left[v]==- || match(left[v])){
left[v]=u; right[u]=v;
return true;
}
}
}
return false;
}
int solve(){
memset(left,-,sizeof(left));
memset(right,-,sizeof(right));
int ans=;
for(int u =; u<n; u++){
memset(S,false,sizeof(S));
memset(T,false,sizeof(T));
if(match(u)) ans++;
}
return ans;
}
}solver;
int main()
{
int cas;
scanf("%d",&cas);
for(int cc =; cc<=cas; ++cc){
int m;
scanf("%d",&m);
for(int i=; i<m; i++){
int th,tm;
scanf("%d:%d%d%d%d%d",&th,&tm,&P[i].sx,&P[i].sy,&P[i].tx,&P[i].ty);
P[i].time = th*+tm;
}
solver.init(m,m);
for(int i=; i<m; i++){
int a1 = abs(P[i].sx-P[i].tx)+abs(P[i].sy-P[i].ty);
for(int j=; j<m; j++){
int a2 = abs(P[i].tx-P[j].sx)+abs(P[i].ty-P[j].sy);
if( (P[i].time+a1+a2) < P[j].time ){
solver.add_edg(i,j);
}
}
}
printf("%d\n",m-solver.solve());
}
return ;
}