poj2060Taxi Cab Scheme(二分图匹配)

/*
   题意： 出租车 有一个出发的时间，从点（a, b）到点（c, d），时间为
   abs(a-c)+abs(b-d)! 一辆车可以在运完一个乘客后运另一个乘客, 
   条件是此车要在预约开始前一分钟之前到达出发地, 问最少需要几辆车
   搞定所有预约。
   
   思路：有向边进行建图，因为出发时间是升序的！
   t0: (a0, b0) ->(c0, d0)表示预约在t0时间出发从(a,b)到(c,d);//节点x 
   t1:  (a1, b1) ->(c1, d1)表示预约在t1时间出发从(a1,b1)到(c1,d1);//节点y 
   
   如果可能的话从t0时间出发的车到达目的地后，如果满足从（c,d)到（a1,b1)
   也就是从第一个目的地到达下一个出发地的时间t2 + 1<=t1, 那么完全就不用
   其他的车再来了！两次的预约都搞定了！ 
   如果满足的话，节点x 和 节点y建立一条有向边！
   最后通过匈牙利算法搞定..... 
*/
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define M 505
using namespace std;

struct point{
   int x, y; 
   point(){}
   point(int x, int y){
      this->x=x;
      this->y=y;          
   }
   int operator -(point a)  {
      return abs(x-a.x) + abs(y-a.y);
   }
};

struct node{
       
     int begin, end;
     point s, d;    
};

node nd[M];
vector<int>v[M];
int vis[M];
int link[M];

int n;

bool dfs(int cur){
   int len=v[cur].size();
   for(int i=0; i<len; ++i){
       int u=v[cur][i];
       if(vis[u]) continue;
       vis[u]=1;
       if(!link[u] || dfs(link[u])){
          link[u]=cur;
          return true;             
       }
   }     
   return false;
}

int main(){
   int t;
   scanf("%d", &t);
   while(t--){
       
       scanf("%d", &n);
       for(int i=1; i<=n; ++i){
           int b, e, x1, y1, x2, y2;
           scanf("%d:%d %d %d %d %d", &b, &e, &x1, &y1, &x2, &y2);
           nd[i].begin=b*60+e;
           nd[i].s=point(x1, y1);
           nd[i].d=point(x2, y2);
           nd[i].end=nd[i].begin+(nd[i].s-nd[i].d);
       } 
       for(int i=1; i<n; ++i)
          for(int j=i+1; j<=n; ++j){
             if(nd[j].begin>=nd[i].end+(nd[i].d-nd[j].s)+1)//如果能够满足条件爱你到达另一个出发地点，两个节点之间建立一条有向边 
                v[i].push_back(j);
          }          
       int ans=0;
       memset(link, 0, sizeof(link));
       for(int i=1; i<=n; ++i){
          memset(vis, 0, sizeof(vis));
          if(dfs(i))  ++ans;     
       }
       cout<<n-ans<<endl;
       for(int i=1; i<=n; ++i)
          v[i].clear();
   }             
   return 0;    
}