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
     
      18 #include
      
       19 #include
       
        20 #include
        
         21 #include
         
          22 #include
          
           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
           
            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
            
             =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<
             
              <