問題:
http://poj.org/problem?id=2060思路:
將每一個Taxi訂單作為頂點，根據題意如果訂單i與訂單j可以在規定時間內到達，那么說頂點i與頂點j存在一條邊
最小路徑覆蓋問題可以轉化為最大匹配問題
見:
http://www.shnenglu.com/Joe/archive/2010/10/21/130676.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 501
5 #define Abs(a) ((a)>=0 ? (a) : (a)*(-1))
6 int M;
7 int graph[MAX_LEN][MAX_LEN];
8 int state[MAX_LEN], fwd[MAX_LEN], bwd[MAX_LEN];
9 struct Taxi {
10 int hour, minu;
11 int sx, sy, dx, dy;
12 }rides[MAX_LEN];
13
14 int
15 reachable(struct Taxi *fst, struct Taxi *scd)
16 {
17 int h, m;
18 h = fst->hour;
19 m = fst->minu + Abs(fst->dx-fst->sx) + Abs(fst->dy-fst->sy) + Abs(scd->sx-fst->dx) + Abs(scd->sy-fst->dy);
20 h = (h+m/60);
21 m = m%60;
22 if(h >= 24)
23 return 0;
24 if(h == scd->hour)
25 return (m<scd->minu);
26 return (h<scd->hour);
27 }
28
29 void
30 build_graph()
31 {
32 int i, j;
33 memset(graph, 0, sizeof(graph));
34 for(i=0; i<M; i++)
35 for(j=i+1; j<M; j++)
36 if(reachable(rides+i, rides+j))
37 graph[i][j] = 1;
38 }
39
40 int
41 find_path(int u)
42 {
43 int i;
44 for(i=0; i<M; i++) {
45 if(graph[u][i] && !state[i]) {
46 state[i] = 1;
47 if(bwd[i]==-1 || find_path(bwd[i])) {
48 bwd[i] = u;
49 fwd[u] = i;
50 return 1;
51 }
52 }
53 }
54 return 0;
55 }
56
57 int
58 MaxMatch()
59 {
60 int i, ans = 0;
61 memset(fwd, -1, sizeof(fwd));
62 memset(bwd, -1, sizeof(bwd));
63 for(i=0; i<M; i++) {
64 if(fwd[i] == -1) {
65 memset(state, 0, sizeof(state));
66 if(find_path(i))
67 ++ans;
68 }
69 }
70 return ans;
71 }
72
73 int
74 main(int argc, char **argv)
75 {
76 int i, tests;
77 scanf("%d", &tests);
78 while(tests--) {
79 scanf("%d", &M);
80 for(i=0; i<M; i++)
81 scanf("%d:%d %d %d %d %d", &rides[i].hour, &rides[i].minu, &rides[i].sx, &rides[i].sy, &rides[i].dx, &rides[i].dy);
82 build_graph();
83 printf("%d\n", M-MaxMatch());
84 }
85 }