最小路徑覆蓋 = |N| - 最大匹配數(shù)
1
#include <cstdio>
2#include <cmath>
3#include <memory.h>
4
5const int SIZE = 501;
6
7struct CAB
8
{
9
int m_sTime, m_eTime;
10 int m_srcX, m_srcY;
11 int m_desX, m_desY;
12
}ride[SIZE];
13
14struct EDGE
15{
16 int m_arr[SIZE];
17 int m_size;
18}edge[SIZE];
19
20int N, time[SIZE][2];
21
22int link[SIZE];
23bool visited[SIZE];
24
25void Init()
26{
27 int i;
28
29 for ( i = 0; i < N; ++i )
30
{
31 edge[i].m_size = 0;
32 link[i] = -1;
33
}
34}
35
36void Build()
37{
38 int i, j, t;
39
40 for ( i = 0; i < N; ++i )
41 for ( j = i + 1; j < N; ++j )
42 {
43 if ( i == j )
44 continue;
45 t = abs(ride[i].m_desX - ride[j].m_srcX) + abs(ride[i].m_desY - ride[j].m_srcY);
46 if ( t + ride[i].m_eTime < ride[j].m_sTime )
47 {
48 edge[i].m_arr[edge[i].m_size++] = j;
49 }
50 }
51}
52
53bool Find( const int& v )
54{
55 int i, x;
56
57 for ( i = 0; i < edge[v].m_size; ++i )
58 {
59 x = edge[v].m_arr[i];
60
61 if ( !visited[x] )
62 {
63 visited[x] = true;
64
65 if ( link[x] == -1 || Find( link[x] ) )
66 {
67 link[x] = v;
68 return true;
69 }
70 }
71 }
72
73 return false;
74}
75
76int main()
77{
78// freopen("1.txt", "r", stdin);
79
80 int test, i, t;
81 char str_time[10];
82
83 scanf("%d", &test);
84
85 while ( test-- )
86 {
87 scanf("%d", &N);
88
89 Init();
90
91 for ( i = 0; i < N; ++i )
92 {
93 scanf("%s %d %d %d %d", str_time, &ride[i].m_srcX, &ride[i].m_srcY,
94 &ride[i].m_desX, &ride[i].m_desY);
95
96 t = (str_time[0] - '0') * 10 + str_time[1] - '0';
97
98 t = t * 60 + (str_time[3] - '0') * 10 + str_time[4] - '0';
99
100 ride[i].m_sTime = t;
101 ride[i].m_eTime = t + abs(ride[i].m_srcX - ride[i].m_desX)
102 + abs(ride[i].m_srcY - ride[i].m_desY);
103 }
104
105 Build();
106
107 t = 0;
108 for ( i = 0; i < N; ++i )
109 {
110 memset(visited, 0, sizeof(visited));
111
112 if ( Find( i ) )
113 t++;
114 }
115
116 t = N - t;
117
118 printf("%d\n", t);
119 }
120 return 0;
121}