The Java Program: C_guards/museumYiu.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 import java.io.*;
23 import java.util.*;
24
25 public class museumYiu
26 {
27 public Scanner in = new Scanner(System.in);
28 public PrintStream out = System.out;
29
30 public int[][] G;
31 public int Gn, n;
32
33 public int Tmax = 24*60;
34 public int slots = Tmax/30;
35
36 public int sor, dst;
37
38 public void main()
39 {
40 int i, j, k, x;
41 int m;
42
43 int start, end;
44 boolean[] can;
45
46 n = in.nextInt();
47 while(n > 0)
48 {
49
50
51 Gn = 2 + n + slots;
52 G = new int[Gn][Gn];
53
54
55 sor = 0; dst = 1;
56
57 for(i=0;i<n;++i)
58 {
59 k = in.nextInt();
60 m = in.nextInt();
61
62
63
64
65 G[sor][guard(i)] = m/30;
66
67
68
69 can = new boolean[Tmax];
70 for(j=0;j<k;++j)
71 {
72
73 start = parse(in.next());
74 end = parse(in.next());
75
76
77 if(start < end)
78 {
79 for(x=start;x<end;++x) can[x] = true;
80 }
81 else
82 {
83
84
85 for(x=start;x<Tmax;++x) can[x] = true;
86 for(x=0;x<end;++x) can[x] = true;
87 }
88 }
89
90
91
92 for(x=0;x<Tmax;x+=30) if(work(can, x, x+30))
93 {
94
95 G[guard(i)][slot(x/30)] = 1;
96 }
97 }
98
99
100 for(j=0;j<slots;++j) G[slot(j)][dst]++;
101
102
103 int res = 0;
104 while(flow() == slots)
105 {
106 ++res;
107
108
109 for(j=0;j<slots;++j) G[slot(j)][dst]++;
110 }
111
112 out.println(res);
113
114 n = in.nextInt();
115 }
116 }
117
118
119 public int guard(int i) { return 2+i; }
120 public int slot(int j) { return 2+n+j; }
121
122
123
124 public int parse(String T)
125 {
126 Scanner p = new Scanner(T);
127 p.useDelimiter(":");
128
129 int hr, min;
130 hr = p.nextInt();
131 min = p.nextInt();
132
133 return hr*60+min;
134 }
135
136
137 public boolean work(boolean[] can, int i, int j)
138 {
139 while(i < j)
140 {
141 if(!can[i]) return false;
142 ++i;
143 }
144 return true;
145 }
146
147
148 public boolean[] visit;
149
150 public int flow()
151 {
152 int ret = 0;
153 int i, x, y;
154
155 visit = new boolean[Gn];
156
157
158 int[] path = dfs(sor, 0);
159 while(path != null)
160 {
161
162 for(i=0;i+1<path.length;++i)
163 {
164 x = path[i];
165 y = path[i+1];
166 G[x][y]--;
167 G[y][x]++;
168 }
169 ret++;
170
171
172 Arrays.fill(visit, false);
173 path = dfs(sor, 0);
174 }
175
176 return ret;
177 }
178
179
180
181 public int[] dfs(int x, int pos)
182 {
183 if(visit[x]) return null;
184 visit[x] = true;
185
186 int[] p;
187 if(x == dst)
188 {
189 p = new int[pos+1];
190 p[pos] = x;
191 return p;
192 }
193
194 int y;
195 for(y=0;y<Gn;++y)
196 {
197 if(G[x][y] > 0)
198 {
199 p = dfs(y, pos+1);
200 if(p != null)
201 {
202 p[pos] = x;
203 return p;
204 }
205 }
206 }
207 return null;
208 }
209
210 public static void main(String[] args)
211 {
212 long startTime = System.currentTimeMillis();
213 (new museumYiu()).main();
214 long endTime = System.currentTimeMillis();
215
216 System.err.println("Time = "+(endTime - startTime)+"(ms)");
217 }
218 }