学步园

//公司有M个顾客，给出每个顾客的发车时间，和起点和终点，如果第i个顾客
//到达之后而第j个顾客还没出发，那么第i辆车就可以去送第j个顾客。。求最少要几辆车。
//这样就比较容易想到最短路径覆盖了。。最短路径覆盖=顶点数-最大匹配数。把可以两个顾客一辆车送的连起来，然后匈牙利算法好了。。
#include <iostream>
#include <math.h>
using namespace std;

struct rode
{
 int a,b,c,d;
 int time;
};

#define MAX 1500
int map[MAX][MAX];
int M;
int mk[MAX];
//从X集合中的顶点u出发用深度优先的策略寻找增广路
//(这种增广路只能使当前的匹配数增加1)
int nx,ny; //X和Y集合中顶点的个数
int cx[MAX],cy[MAX];
//cx[i]表示最终求得的最大匹配中与Xi匹配的Y顶点, cy[i]同理
int path(int u)
{
 for(int v=0; v<ny; v++) //考虑所有Yi顶点v
 {
  if(map[u][v]&&!mk[v])
  {
   mk[v]=1;
   //如果v没有匹配,或者如果v已经匹配了，
   //但从y[v]出发可以找到一条增广路
   if(cy[v]==-1|| path(cy[v]))
   {
    cx[u] = v; //把v匹配给u
    cy[v] = u; //把u匹配给v
    return 1; //找到可增广路
   }
  }
 }
 return 0 ; //如果不存在从u出发的增广路
}
int MaxMatch() //求二部图最大匹配的匈牙利算法
{
 int res=0;
 memset(cx,0xff,sizeof(cx)); //从0匹配开始增广
 memset(cy,0xff,sizeof(cy));
 for(int i=0; i<nx; i++)
 {
  if(cx[i]==-1) //从每个未盖点出发进行寻找增广路
  {
   memset(mk,0,sizeof(mk));
   res+=path(i); //每找到一条增广路，可使得匹配数加1
  }
 }
 return res;
}

rode RODE[1500];

int main()
{
 int t;
 int i,j;
 int hour,minute;
 while(cin>>t)
 {
  for(int h=0;h<t;h++)
  {
   memset(map,0,sizeof(map));
   cin>>M;
   nx=ny=M;
   for(i=0;i<M;i++)
   {
    cin>>hour;
    scanf(":");
    cin>>minute>>RODE[i].a>>RODE[i].b>>RODE[i].c>>RODE[i].d;
    //  cout<<hour<<":"<<minute<<" "<<RODE[i].a<<" "<<RODE[i].b<<" "<<RODE[i].c<<" "<<RODE[i].d;
    RODE[i].time=hour*60+minute;
   }
   for(i=0;i<M;i++)
    for(j=0;j<M;j++)
    {
     if(i!=j)
     {
      int cost1,cost2;
      cost1=abs(RODE[i].a-RODE[i].c)+abs(RODE[i].b-RODE[i].d);
      cost2=abs(RODE[i].c-RODE[j].a)+abs(RODE[i].d-RODE[j].b);
     // cout<<"i="<<i<<" "<<"j="<<j<<" "<<cost1<<" "<<cost2<<endl;
     // cout<<RODE[i].time<<" "<<RODE[j].time<<endl;
      if(RODE[i].time+cost1+cost2+1<=RODE[j].time)
      {
       map[i][j]=1;
      // cout<<"****"<<endl;
      }
     }
    }
    
   /* for(i=0;i<M;i++)
    {
     cout<<endl;
     for(j=0;j<M;j++)
      cout<<map[i][j]<<" ";
    }*/
    int sum=MaxMatch();
    // cout<<sum<<endl;
    cout<<M-sum<<endl;
  }
 }
 return 0;
}