对于什么是DAG最小路径覆盖以及解题方法在我的另外的博客已经有了。http://www.cnblogs.com/Potato-lover/p/3980470.html
此题的题意：
公交车（出租车）车站有一个固定的发车时间，有二维起点和终点，花费的时间是两点的曼哈顿距离，即|x1-x2| + |y1-y2| 。问最少需要多少辆车才能跑完所有路线。
思路：
A站点发车时间如果大于车到达B站点的时间与车从B站点到达A站点的时间，就可以连边。然后求最大匹配。最小路径覆盖 = 顶点数 - 最大匹配
有个小地方要注意，上面说的“大于”，那么等于可不可以呢？按样例2，等于是不可以的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=,INF=0x3f3f3f3f;
int bmap[N][N],cx[N],cy[N],dx[N],dy[N];
bool bmask[N];
int nx,ny,dis,ans;
bool searchpath()
{
queue<int> q;
dis=INF;
memset(dx,-,sizeof(dx));
memset(dy,-,sizeof(dy));
for(int i=;i<=nx;i++)
{
if(cx[i]==-){ q.push(i); dx[i]=; }
while(!q.empty())
{
int u=q.front(); q.pop();
if(dx[u]>dis) break;
for(int v=;v<=ny;v++)
{
if(bmap[u][v]&&dy[v]==-)
{
dy[v]= dx[u] + ;
if(cy[v]==-) dis=dy[v];
else
{
dx[cy[v]]= dy[v]+;
q.push(cy[v]);
}
}
}
}
}
return dis!=INF;
}
int findpath(int u)
{
for(int v=;v<=ny;v++)
{
if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+)
{
bmask[v]=;
if(cy[v]!=-&&dy[v]==dis) continue;
if(cy[v]==-||findpath(cy[v]))
{
cy[v]=u; cx[u]=v;
return ;
}
}
}
return ;
}
void maxmatch()
{
ans=;
memset(cx,-,sizeof(cx));
memset(cy,-,sizeof(cy));
while(searchpath())
{
memset(bmask,,sizeof(bmask));
for(int i=;i<=nx;i++)
if(cx[i]==-) ans+=findpath(i);
}
}
void init()
{
memset(bmap,,sizeof(bmap));
}
struct node
{
int x,y,a,b,s,t;
}e[N];
int main()
{
//freopen("test.txt","r",stdin);
int i,j,k,n,cas,s,t,a,b;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
init();
for(i=;i<=n;i++){
scanf("%d:%d",&a,&b);
e[i].s=a*+b;
scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);
e[i].t= e[i].s+abs(e[i].a +-e[i].x)+abs(e[i].b-e[i].y);
}
for(i=;i<=n;i++){
for(j=;j<=n;j++){
if(i==j) continue;
t=abs(e[j].x-e[i].a)+abs(e[j].y-e[i].b);
if(e[j].s>e[i].t+t) bmap[i][j]=;
t=abs(e[i].x-e[j].a)+abs(e[i].y-e[j].b);
if(e[i].s>e[j].t+t) bmap[j][i]=;
}
}
nx=ny=n;
maxmatch();
printf("%d\n",n-ans);
}
return ;
}