1 /* 2    题意： 出租车 有一个出发的时间，从点（a, b）到点（c, d），时间为 3    abs(a-c)+abs(b-d)! 一辆车可以在运完一个乘客后运另一个乘客,  4    条件是此车要在预约开始前一分钟之前到达出发地, 问最少需要几辆车 5    搞定所有预约。 6     7    思路：有向边进行建图，因为出发时间是升序的！ 8    t0: (a0, b0) ->(c0, d0)表示预约在t0时间出发从(a,b)到(c,d);//节点x  9    t1:  (a1, b1) ->(c1, d1)表示预约在t1时间出发从(a1,b1)到(c1,d1);//节点y 10    11    如果可能的话从t0时间出发的车到达目的地后，如果满足从（c,d)到（a1,b1)12    也就是从第一个目的地到达下一个出发地的时间t2 + 1<=t1, 那么完全就不用13    其他的车再来了！两次的预约都搞定了！ 14    如果满足的话，节点x 和 节点y建立一条有向边！15    最后通过匈牙利算法搞定..... 16 */17 #include<iostream>18 #include<cmath>19 #include<cstdio>20 #include<cstring>21 #include<algorithm>22 #include<vector>23 #define M 50524 using namespace std;25 26 struct point{27    int x, y; 28    point(){}29    point(int x, int y){30       this->x=x;31       this->y=y;          32    }33    int operator -(point a)  {34       return abs(x-a.x) + abs(y-a.y);35    }36 };37 38 struct node{39        40      int begin, end;41      point s, d;    42 };43 44 node nd[M];45 vector<int>v[M];46 int vis[M];47 int link[M];48 49 int n;50 51 bool dfs(int cur){52    int len=v[cur].size();53    for(int i=0; i<len; ++i){54        int u=v[cur][i];55        if(vis[u]) continue;56        vis[u]=1;57        if(!link[u] || dfs(link[u])){58           link[u]=cur;59           return true;             60        }61    }     62    return false;63 }64 65 int main(){66    int t;67    scanf("%d", &t);68    while(t--){69        70        scanf("%d", &n);71        for(int i=1; i<=n; ++i){72            int b, e, x1, y1, x2, y2;73            scanf("%d:%d %d %d %d %d", &b, &e, &x1, &y1, &x2, &y2);74            nd[i].begin=b*60+e;75            nd[i].s=point(x1, y1);76            nd[i].d=point(x2, y2);77            nd[i].end=nd[i].begin+(nd[i].s-nd[i].d);78        } 79        for(int i=1; i<n; ++i)80           for(int j=i+1; j<=n; ++j){81              if(nd[j].begin>=nd[i].end+(nd[i].d-nd[j].s)+1)//如果能够满足条件爱你到达另一个出发地点，两个节点之间建立一条有向边 82                 v[i].push_back(j);83           }          84        int ans=0;85        memset(link, 0, sizeof(link));86        for(int i=1; i<=n; ++i){87           memset(vis, 0, sizeof(vis));88           if(dfs(i))  ++ans;     89        }90        cout<<n-ans<<endl;91        for(int i=1; i<=n; ++i)92           v[i].clear();93    }             94    return 0;    95 }