POJ 2060 最小路径覆盖

题意：

给出一个T 代表有T组样例

一个n 代表有n个任务

然后接下来n 个任务给出出发时间和出发地点(a, b)以及目的地(c, d) 从出发地到目的地花费时间为 |a - c| + |b - d|

问最少用多少辆车可以完成所有任务

思路：

根据第 i 个任务结束时间+从第 i 个任务的目的地到第 j 个任务的出发地 < 第 j 个任务的开始时间

确立这两个任务是否可以连通..如果可以就连线

然后求出最大匹配

任务数 - 最大匹配 = 最短路径覆盖

Tips：

no tips..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #define clr(x) memset(x, 0, sizeof(x))
 4 #define fabs(x) ((x) > 0?(x):-(x))
 5 
 6 const int INF = 0x1f1f1f1f;
 7 
 8 struct Ride
 9 {
10     int start;
11     int end;
12     int a, b, c, d;
13 }ride[510];
14 
15 struct Edge
16 {
17     int next;
18     int to;
19 }edge[1000000];
20 int tot;
21 int head[510];
22 
23 void add(int s, int u)
24 {
25     edge[tot].to = u;
26     edge[tot].next = head[s];
27     head[s] = tot++;
28 }
29 
30 
31  int link[510];
32  int vis[510];
33  int sum, n;
34 
35  int dfs(int x)
36  {
37      for(int i = head[x]; i != 0; i = edge[i].next){
38          int y = edge[i].to;
39          if(!vis[y]){
40              vis[y] = true;
41              if(link[y] == 0 || dfs(link[y])){
42                  link[y] = x;
43                  return true;
44              }
45          }
46      }
47      return false;
48  }
49 
50  void solve()
51  {
52      clr(link);
53      sum = 0;
54      for(int i = 1; i <= n; ++i){
55          clr(vis);
56          if(dfs(i))
57              sum++;
58      }
59  }
60 
61 
62 int main()
63 {
64     int i, j, k;
65     int T;
66     int h, m;
67     while(scanf("%d", &T) != EOF)
68     while(T--)
69     {
70         tot = 1;
71         clr(head);
72 
73         scanf("%d", &n);
74         for(i = 1; i <= n; ++i){
75             scanf("%d:%d %d %d %d %d", &h, &m, &ride[i].a, &ride[i].b, &ride[i].c, &ride[i].d);
76             ride[i].start = h*60+m;
77             ride[i].end = ride[i].start + fabs(ride[i].a-ride[i].c)+fabs(ride[i].b-ride[i].d);
78         }
79 
80         for(i = 1; i <= n; ++i)
81         for(j = 1; j <= n; ++j)
82         if(ride[i].end + fabs(ride[i].c-ride[j].a)+fabs(ride[i].d-ride[j].b) < ride[j].start)
83         add(i, j);
84 
85         solve();
86 
87         printf("%d\n", n-sum);
88     }
89     return 0;
90 }