The Java Program: C_guards/museumYiu.java

  1 /*
  2 ACM ICPC Southeast Regional Contest 2009
  3 
  4 Guarding A Museum
  5 
  6 Author: Yiu Yu Ho
  7 
  8 This is a traditional supply and demand problem (transportation problem). For more information please reference 
  9 Network Flows: Theory, Algorithms, and Applications
 10 Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
 11 
 12 Since the guards can only switch at half hours, we may consider the day as a partition 24 x 2 = 48 half hour 
 13 slots total, where each slot requires some guard to be on duty.
 14 Each guard provides exactly maxTime/30 supplies as s/he can guard at most that many slots, where maxTime is the 
 15 maximum number of minutes s/he is able to be on duty, in addition, s/he can only guard the corresponding slots 
 16 where she is completely available.  Each slot, has a demand of k units, where k is the number of guards the museum 
 17 is trying to maintain.
 18 
 19 The supply and demand problem is solved using network flow, see details below
 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                         //source, sink, n guards, slots number of slots
 50                         //Gn is the number of vertices in the network
 51                         Gn = 2 + n + slots;
 52                         G = new int[Gn][Gn];
 53                         
 54                         //source is vertex 0 and sink (dst) is vertex 1
 55                         sor = 0; dst = 1;
 56 
 57                         for(i=0;i<n;++i)
 58                         {
 59                                 k = in.nextInt();
 60                                 m = in.nextInt();
 61                                 
 62                                 //source --> i-th guard has capacity m/30, where m is the maximium number of 
 63                                 //minutes guard i is able to work.  This limits the number of times a guard is 
 64                                 //assigned to any slots.
 65                                 G[sor][guard(i)] = m/30;
 66                                 
 67                                 //read in time intervals, the union of time intervals are kept track with an array of 1440 cells,
 68                                 //one per minute
 69                                 can = new boolean[Tmax];
 70                                 for(j=0;j<k;++j)
 71                                 {
 72                                         //parse converts from HH:MM to [0, 1439]
 73                                         start = parse(in.next());
 74                                         end = parse(in.next());
 75                                         
 76                                         //start < end, the time interval is [start, end)
 77                                         if(start < end)
 78                                         {
 79                                                 for(x=start;x<end;++x) can[x] = true;
 80                                         }
 81                                         else //start >= end
 82                                         {
 83                                                 //start >= end, we break it down into [start, 1440) and [0, end)
 84                                                 //warping around mid-night
 85                                                 for(x=start;x<Tmax;++x) can[x] = true;
 86                                                 for(x=0;x<end;++x) can[x] = true;
 87                                         }
 88                                 }
 89                                 
 90                                 //Guard i can work at a slot, if he can work during its entirety.
 91                                 //The work method checks that.
 92                                 for(x=0;x<Tmax;x+=30) if(work(can, x, x+30))
 93                                 {
 94                                         //capacity = 1, as the guard can only contribute 1 unit to the demand of a slot.
 95                                         G[guard(i)][slot(x/30)] = 1;
 96                                 }
 97                         }//end for i = 0 .. n-1
 98                         
 99                         //Try k = 1
100                         for(j=0;j<slots;++j) G[slot(j)][dst]++;
101                         
102                         //There is a feasible solution for maintaining k guards as long as the maximum flow equals k * slots.
103                         int res = 0;
104                         while(flow() == slots)
105                         {
106                                 ++res;
107                                 //check the next k, note that we do not need to reset our residual network because augmenting path 
108                                 //algorithm (Ford-Fulkerson, Edmonds-Karp, etc) has no preference on how each (sor,dst)-path is selected
109                                 for(j=0;j<slots;++j) G[slot(j)][dst]++;
110                         }
111 
112                         out.println(res);
113 
114                         n = in.nextInt();
115                 }//end while(n > 0)
116         }//end public void main()
117 
118         //0 - sor, 1 - dst, [2 .. 2+n-1] - guards, [2+n .. 2+n+48-1] - slots
119         public int guard(int i) { return 2+i; }
120         public int slot(int j) { return 2+n+j; }
121         
122         //convert a time in HH:MM format to [0, 1439], an integer representing the number of 
123         //minutes from mid-night
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         //check if can[i..j) are all true
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         //Network Flow code below
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                 //get an augmentng path
158                 int[] path = dfs(sor, 0);
159                 while(path != null)
160                 {
161                         //augment
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                         //get new path
172                         Arrays.fill(visit, false);
173                         path = dfs(sor, 0);
174                 }
175 
176                 return ret;
177         }//public int flow()
178         
179         //Depth first search, returns a path from sor to dst, where the current vertex is x, 
180         //at position pos of the path
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         }//public int[] dfs(int x, int pos)
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 }