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
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
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
172
173 return found;
174 }
175
176 public boolean gotorow( int i, int j, boolean up )
177 {
178
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
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
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
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
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
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
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
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
339 boolean looped = gotocol( i, j, true );
340 if( !looped )
341 {
342 Arrays.fill( rowvisited, false );
343 Arrays.fill( colvisited, false );
344
345
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
361 System.out.printf( matrix[i][j]>=0 ? " %3d " : " [%3d]", value );
362 ps.print( (j==0?"":" ") + value );
363 }
364 System.out.println();
365 ps.println();
366 }
367 }
368 }
369
370
371
372
373
374
375
376 public static void main( String[] args ) throws Exception
377 {
378 new datarecoverysave().doit();
379 }
380
381 }