The Java Program: C_recovery/datarecoverysave.java

  1 import java.io.*;
  2 import java.util.*;
  3 
  4 public class datarecoverysave
  5 {
  6     public Scanner sc;
  7     public PrintStream ps;
  8         
  9     public class Node
 10     {
 11         public boolean visited = false;
 12         public LinkedList<Edge> edges = new LinkedList<Edge>();
 13         public Edge gothere = null;
 14     }
 15     
 16     public class Edge
 17     {
 18         Node destination;
 19         int capacity;
 20         Edge dual;
 21         
 22         public Edge( Node d, int c )
 23         {
 24                 capacity = c;
 25                 destination = d;
 26                 dual = null;
 27         }
 28     }
 29     
 30     public void link( Node n1, Node n2, int cost )
 31     {
 32         Edge e12 = new Edge( n2, cost );
 33         Edge e21 = new Edge( n1, 0 );
 34         e12.dual = e21;
 35         e21.dual = e12;
 36         n1.edges.add( e12 );
 37         n2.edges.add( e21 );
 38     }
 39     
 40     public LinkedList<Node> queue = new LinkedList<Node>();
 41     
 42     public int fordfulkerson( Node src, Node snk, List<Node> nodes )
 43     {
 44         int total = 0;
 45         
 46         for(;;)
 47         {  
 48             for( Node node : nodes )
 49             {
 50                 node.visited = false;
 51                 node.gothere = null;
 52             }
 53 
 54             queue.clear();
 55             queue.add( src );
 56             src.visited = true;
 57             boolean found = false;
 58             while( queue.size()>0 )
 59             {
 60                 Node node = queue.poll();
 61                 if( node==snk )
 62                 {
 63                         found = true;
 64                         break;
 65                 }
 66                 
 67                 for( Edge edge : node.edges )
 68                 {
 69                         Node dest = edge.destination;
 70                     if( edge.capacity>0 && !dest.visited )
 71                     {
 72                         dest.visited = true;
 73                         dest.gothere = edge;
 74                         queue.add( dest );
 75                     }
 76                 }
 77             }
 78             
 79             if( !found ) break;
 80             
 81             int min = Integer.MAX_VALUE;
 82             for( Node node = snk; node.gothere != null; )
 83             {
 84                 Edge edge = node.gothere;
 85                 if( edge.capacity < min ) min = edge.capacity;
 86                 node = edge.dual.destination;
 87             }
 88             
 89             total += min;
 90             
 91             for( Node node = snk; node.gothere != null; )
 92             {
 93                 Edge edge = node.gothere;
 94                 edge.capacity -= min;
 95                 edge.dual.capacity += min;
 96                 node = edge.dual.destination;
 97             }            
 98         }
 99         
100         return total;
101     }
102     
103     public int getvalue( Node varnodes[], Node rownodes[], int n )
104     {
105         int value = -1;
106         
107         Node node = varnodes[n];    
108         for( Edge edge : node.edges )
109         {
110             for( Node dest : rownodes )
111             {
112                 if( edge.destination == dest )
113                 {
114                     value = edge.capacity;
115                     break;
116                 }
117             }
118         }
119         
120         return value;
121     }
122     
123     public boolean visited[][] = new boolean[50][50];
124     public int matrix[][] = new int[50][50];
125     public int values[][] = new int[50][50];
126     public int rowtotals[] = new int[50];
127     public int rowcounts[] = new int[50];
128     public int coltotals[] = new int[50];
129     public int colcounts[] = new int[50];
130     public boolean rowvisited[] = new boolean[50];
131     public boolean colvisited[] = new boolean[50];
132     public int ipath[] = new int[50*50];
133     public int jpath[] = new int[50*50];
134     public int n, m;
135     
136     public void dump()
137     {
138         for( int i=0; i<n; i++ )
139         {
140             for( int j=0; j<m; j++ )
141             {
142                 System.out.printf( " %2d", matrix[i][j] );
143             }
144             System.out.println();
145         }
146         System.out.println();
147         System.out.println( Arrays.toString( rowtotals ) );
148         System.out.println( Arrays.toString( coltotals ) );
149         System.out.println();
150     }
151     
152     public int starti;
153     
154     public boolean gotocol( int i, int j, boolean up )
155     {
156         //System.out.println(  "col using [" + i + "," + j +  "]" );
157         boolean found = false;
158         if( !colvisited[j] )
159         {
160             if( (up&&values[i][j]<100) || (!up&&values[i][j]>0) )
161             {
162                 colvisited[j] = true;
163                 //System.out.println( "Col: " + i + " " + j );
164                 
165                 for( int k=0; k<n && !found; k++ ) if( k!=i )
166                 {
167                     if( matrix[k][j]<0 && !rowvisited[k] ) found = gotorow( k, j, !up );
168                 }  
169             }
170         }
171         //System.out.println(  "exiting col using [" + i + "," + j +  "]" );
172                 
173         return found;
174     }
175     
176     public boolean gotorow( int i, int j, boolean up  )
177     {
178         //System.out.println(  "row using [" + i + "," + j +  "]" );
179         boolean found = false;
180         if( !rowvisited[i] )
181         {
182             if( (up&&values[i][j]<100) || (!up&&values[i][j]>0) )
183             {
184                 found = i==starti;
185                 rowvisited[i] = true;
186                 //System.out.println( "Row: " + i + " " + j );
187                 
188                 for( int k=0; k<m && !found; k++ ) if( k!=j )
189                 {
190                     if( matrix[i][k]<0 && !colvisited[k] ) found = gotocol( i, k, !up );
191                 }  
192             }
193         }
194         //System.out.println(  "exiting row using [" + i + "," + j +  "]" );
195         return found;
196     }
197     
198     public void fix( int i, int j, int value )
199     {
200         matrix[i][j] = value;
201         rowtotals[i] -= value;
202         --rowcounts[i];
203         coltotals[j] -= value;
204         --colcounts[j];
205     }
206 
207     /**
208      * Driver for the max flow strategy 
209      */
210     public void doit() throws Exception
211     {
212         sc = new Scanner( new File( "datarecovery.judge" ) );
213         ps = new PrintStream( new FileOutputStream( "datarecovery.out" ) ); 
214         
215         for(;;)
216         {
217                 n = sc.nextInt();
218                 m = sc.nextInt();
219                 if( n==0 ) break;
220                 
221                 int nvars = 0;
222                 for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ )
223                 {
224                         int value = sc.nextInt();
225                         matrix[i][j] = value;
226                         if( value==-1 ) ++nvars;
227                 }
228                 
229                 for( int i=0; i<n; i++ )
230                 {
231                         rowtotals[i] = sc.nextInt();
232                         rowcounts[i] = m;
233                 }
234                 
235                 for( int j=0; j<m; j++ )
236                 {
237                         coltotals[j] = sc.nextInt();
238                         colcounts[j] = n;
239                 }
240                 
241                 //dump();
242                 
243                 for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ )
244                 {
245                     if( matrix[i][j]>0 )
246                     {
247                         fix( i, j, matrix[i][j] );
248                     }
249                 }
250                 
251                 //dump();
252                 
253                 LinkedList<Node> nodes = new LinkedList<Node>();
254                 Node source = new Node();
255                 nodes.add( source );
256                 Node sink = new Node();
257                 nodes.add( sink );
258                 
259                 Node rownodes[] = new Node[n];
260                 for( int i=0; i<n; i++ )
261                 {
262                         rownodes[i] = new Node();
263                         nodes.add( rownodes[i] );
264                         link( source, rownodes[i], rowtotals[i] );
265                 }
266                 
267                 Node colnodes[] = new Node[m];
268                 for( int j=0; j<m; j++ )
269                 {
270                         colnodes[j] = new Node();
271                         nodes.add( colnodes[j] );
272                         link( colnodes[j], sink, coltotals[j] );
273                 }
274                 
275                 int count = 0;
276                 Node varnodes[] = new Node[nvars];
277                 for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ ) if( matrix[i][j]==-1 )
278                 {
279                         varnodes[count] = new Node();
280                         nodes.add( varnodes[count] );
281                         link( rownodes[i], varnodes[count], 100 );
282                         link( varnodes[count], colnodes[j], 100 ); 
283                         ++count;
284                 }
285                 
286                 int target = fordfulkerson( source, sink, nodes );              
287                 
288                 for( int i=0; i<visited.length; i++ )
289                 {
290                     Arrays.fill( visited[i], false );
291                     Arrays.fill( values[i], -1 );
292                 }
293                 
294                 count = 0;
295                 for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ ) if( matrix[i][j]<0 )
296                 {
297                     values[i][j] = getvalue( varnodes, rownodes, count++ );
298                 }  
299                 
300 //            boolean changed = false;
301 //            do
302 //            {
303 //                changed = false;
304 //                for( int i=0; i<n; i++ ) if( rowcounts[i]>0 )
305 //                {
306 //                    if( rowcounts[i]==1 || rowtotals[i]==0 || rowtotals[i]==100*rowcounts[i] )
307 //                    {
308 //                        for( int j=0; j<m; j++ ) if( matrix[i][j]<0 )
309 //                        {
310 //                            fix( i, j, values[i][j] );
311 //                            changed = true;
312 //                        }
313 //                    }
314 //                }
315 //                
316 //                for( int j=0; j<m; j++ ) if( colcounts[j]>0 )
317 //                {
318 //                    if( colcounts[j]==1 || coltotals[j]==0 || colcounts[j]==100*colcounts[j] )
319 //                    {
320 //                        for( int i=0; i<n; i++ ) if( matrix[i][j]<0 )
321 //                        {
322 //                            fix( i, j, values[i][j] );
323 //                            changed = true;
324 //                        }
325 //                    }
326 //                }
327 //            }
328 //            while( changed );
329                 
330                 for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ )
331                 {
332                     if( matrix[i][j]<0  )
333                     {
334                         starti = i;
335                     Arrays.fill( rowvisited, false );
336                     Arrays.fill( colvisited, false );
337                     
338                     //System.out.println( "Starting at " + i + " " + j  );
339                         boolean looped = gotocol( i, j, true );
340                         if( !looped )
341                         {
342                         Arrays.fill( rowvisited, false );
343                         Arrays.fill( colvisited, false );
344                         
345                         //System.out.println( "Starting at " + i + " " + j  );
346                         looped = gotocol( i, j, false );
347                         }
348                         if( looped )
349                         {
350                             matrix[i][j] = -2;
351                         }
352                     }
353                 }
354                 
355                 for( int i=0; i<n; i++ )
356                 {
357                         for( int j=0; j<m; j++ )
358                         {
359                     int value = matrix[i][j]==-2 ? -1 : matrix[i][j]==-1 ? values[i][j] : matrix[i][j];
360                     //int value = matrix[i][j]<0 ? values[i][j] : matrix[i][j];
361                     System.out.printf(  matrix[i][j]>=0 ? "  %3d " : " [%3d]", value );//(j==0?"":" ") + value );
362                                 ps.print( (j==0?"":" ") + value );
363                         }
364                         System.out.println();
365                         ps.println();
366                 }
367         }
368     }
369           
370     /**
371      * The main just creates an object and calls doit().
372      * 
373      * @param args Command line args, necessary but unused.
374      * @throws Exception
375      */
376     public static void main( String[] args ) throws Exception
377     {
378         new datarecoverysave().doit();
379     }
380 
381 }