|
1 /*** Copyright 1989 Norbert Schlenker. All rights reserved. |
|
2 |
|
3 *** This software is distributed subject to the following provisions: |
|
4 *** - this notice may not be removed; |
|
5 *** - you may modify the source code, as long as redistributed |
|
6 *** versions have their modifications clearly marked; |
|
7 *** - no charge, other than a nominal copying fee, may be made |
|
8 *** when providing copies of this source code to others; |
|
9 *** - if this source code is used as part of a product which is |
|
10 *** distributed only as a binary, a copy of this source code |
|
11 *** must be included in the distribution. |
|
12 *** |
|
13 *** Unlike the GNU GPL, use of this code does not obligate you to |
|
14 *** disclose your own proprietary source code. |
|
15 |
|
16 *** The author of this software provides no warranty, express or |
|
17 *** implied, as to its utility or correctness. That said, reports |
|
18 *** of bugs or compatibility problems will be gladly received by |
|
19 *** nfs@princeton.edu, and fixes will be attempted. |
|
20 ***/ |
|
21 |
|
22 |
|
23 /*** netgen - C version of the standard NETGEN network generator |
|
24 *** This program is a functional equivalent of the |
|
25 *** standard network generator NETGEN described in: |
|
26 *** Klingman, D., A. Napier, and J. Stutz, "NETGEN: A Program |
|
27 *** for Generating Large Scale Capacitated Assignment, |
|
28 *** Transportation, and Minimum Cost Flow Network Problems", |
|
29 *** Management Science 20, 5, 814-821 (1974) |
|
30 *** |
|
31 *** This software provides a number of interfaces for use by |
|
32 *** network solvers. Standard call interfaces are supplied for |
|
33 *** use by (Unix) C and Fortran solvers, with generation parameters |
|
34 *** passed into the generator and the flow network passed back to |
|
35 *** the solver via large external (COMMON in Fortran) arrays. |
|
36 *** For the DIMACS challenge, this code will produce output files |
|
37 *** in the appropriate format for later reading by solvers. |
|
38 *** Undefine the symbol DIMACS when using the call interface. |
|
39 *** |
|
40 *** The generator produces exact duplicates of the networks |
|
41 *** made by the Fortran code (even though that means bugs |
|
42 *** are being perpetuated). It is faster by orders of magnitude |
|
43 *** in generating large networks, primarily by imposing the |
|
44 *** notion of the abstract data type INDEX_LIST and implementing |
|
45 *** the type operations in a reasonably efficient fashion. |
|
46 ***/ |
|
47 |
|
48 /*** Generates transportation problems if: |
|
49 *** SOURCES+SINKS == NODES && TSOURCES == TSINKS == 0 |
|
50 *** |
|
51 *** Generates assignment problems if above conditions are satisfied, and: |
|
52 *** SOURCES == SINKS && SUPPLY == SOURCES |
|
53 *** |
|
54 *** Generates maximum flow problems if not an assignment problem and: |
|
55 *** MINCOST == MAXCOST == 1 |
|
56 |
|
57 *** Implementation notes: |
|
58 *** |
|
59 *** This file contains both a Fortran and a C interface. The |
|
60 *** Fortran interface is suffixed with an underscore to make it |
|
61 *** callable in the normal fashion from Fortran (a Unix convention). |
|
62 *** |
|
63 *** Because Fortran has no facility for pointers, the common arrays |
|
64 *** are statically allocated. Static allocation has nothing to recommend |
|
65 *** it except for the need for a Fortran interface. |
|
66 *** |
|
67 *** This software expects input parameters to be long integers |
|
68 *** (in the sense of C); that means no INTEGER*2 from Fortran callers. |
|
69 *** |
|
70 *** Compiling with -DDIMACS produces a program that reads problem |
|
71 *** parameters, generates the appropriate problem, and prints it. |
|
72 *** |
|
73 *** Compiling with -DDEBUG produces code with externally visible |
|
74 *** procedure names, useful for debugging and profiling. |
|
75 ***/ |
|
76 |
|
77 |
|
78 /*** System interfaces */ |
|
79 |
|
80 #include <stdio.h> |
|
81 |
|
82 |
|
83 /*** Public interfaces */ |
|
84 |
|
85 #define ALLOCATE_NETWORK |
|
86 #include "netgen.h" |
|
87 |
|
88 #define PROBLEM_PARMS 13 /* aliases for generation parameters */ |
|
89 #define NODES parms[0] /* number of nodes */ |
|
90 #define SOURCES parms[1] /* number of sources (including transshipment) */ |
|
91 #define SINKS parms[2] /* number of sinks (including transshipment) */ |
|
92 #define DENSITY parms[3] /* number of (requested) arcs */ |
|
93 #define MINCOST parms[4] /* minimum cost of arcs */ |
|
94 #define MAXCOST parms[5] /* maximum cost of arcs */ |
|
95 #define SUPPLY parms[6] /* total supply */ |
|
96 #define TSOURCES parms[7] /* transshipment sources */ |
|
97 #define TSINKS parms[8] /* transshipment sinks */ |
|
98 #define HICOST parms[9] /* percent of skeleton arcs given maximum cost */ |
|
99 #define CAPACITATED parms[10] /* percent of arcs to be capacitated */ |
|
100 #define MINCAP parms[11] /* minimum capacity for capacitated arcs */ |
|
101 #define MAXCAP parms[12] /* maximum capacity for capacitated arcs */ |
|
102 |
|
103 |
|
104 /*** Private interfaces */ |
|
105 |
|
106 #ifdef DEBUG |
|
107 #define PRIVATE |
|
108 #else |
|
109 #define PRIVATE static |
|
110 #endif |
|
111 |
|
112 #ifdef __STDC__ |
|
113 PRIVATE void create_supply(NODE, CAPACITY); /* create supply nodes */ |
|
114 PRIVATE void create_assignment(long*); /* create assignment problem */ |
|
115 PRIVATE void sort_skeleton(int); /* sorts skeleton chains */ |
|
116 PRIVATE void pick_head(long*, int, NODE); /* choose destination nodes for rubbish arcs */ |
|
117 PRIVATE void error_exit(long); /* print error message and exit */ |
|
118 #else |
|
119 PRIVATE void create_supply(); /* create supply nodes */ |
|
120 PRIVATE void create_assignment(); /* create assignment problem */ |
|
121 PRIVATE void sort_skeleton(); /* sorts skeleton chains */ |
|
122 PRIVATE void pick_head(); /* chooses destination nodes for rubbish arcs */ |
|
123 PRIVATE void error_exit(); /* print error message and exit */ |
|
124 #endif |
|
125 |
|
126 /*** Private variables */ |
|
127 |
|
128 static NODE nodes_left; |
|
129 static ARC arc_count; |
|
130 static NODE pred[MAXARCS]; |
|
131 static NODE head[MAXARCS]; |
|
132 static NODE tail[MAXARCS]; |
|
133 |
|
134 |
|
135 /*** Local macros */ |
|
136 |
|
137 #define MIN(x, y) ((x) < (y) ? (x) : (y)) |
|
138 #define MAX(x, y) ((x) > (y) ? (x) : (y)) |
|
139 #define SAVE_ARC(tail, head, cost, capacity) /* records an arc where our caller can get it */ \ |
|
140 { \ |
|
141 FROM[arc_count] = tail; \ |
|
142 TO [arc_count] = head; \ |
|
143 C [arc_count] = cost; \ |
|
144 U [arc_count] = capacity; \ |
|
145 arc_count++; \ |
|
146 } |
|
147 |
|
148 |
|
149 /*** Fortran callable interface routine */ |
|
150 |
|
151 void netgen_(seed, parms, generated_nodes, generated_arcs) |
|
152 long* seed; /* pointer to random seed */ |
|
153 long parms[PROBLEM_PARMS]; /* problem parameters */ |
|
154 long* generated_nodes; /* number of generated nodes */ |
|
155 long* generated_arcs; /* number of generated arcs */ |
|
156 { |
|
157 *generated_nodes = NODES; |
|
158 if ((*generated_arcs = netgen(*seed, parms)) < 0) |
|
159 error_exit(*generated_arcs); |
|
160 } |
|
161 |
|
162 |
|
163 /*** C callable interface routine */ |
|
164 |
|
165 ARC netgen(seed, parms) |
|
166 long seed; /* random seed */ |
|
167 long parms[]; /* problem parameters */ |
|
168 { |
|
169 register NODE i,j,k; |
|
170 NODE source; |
|
171 NODE node; |
|
172 NODE sinks_per_source; |
|
173 NODE* sinks; |
|
174 NODE it; |
|
175 int chain_length; |
|
176 COST cost; |
|
177 CAPACITY cap; |
|
178 INDEX_LIST handle; |
|
179 int supply_per_sink; |
|
180 int partial_supply; |
|
181 int sort_count; |
|
182 |
|
183 |
|
184 /*** Perform sanity checks on the input */ |
|
185 |
|
186 if (seed <= 0) |
|
187 return BAD_SEED; |
|
188 if (NODES > MAXNODES || DENSITY > MAXARCS) |
|
189 return TOO_BIG; |
|
190 if ((NODES <= 0) || |
|
191 (NODES > DENSITY) || |
|
192 (SOURCES <= 0) || |
|
193 (SINKS <= 0) || |
|
194 (SOURCES + SINKS > NODES) || |
|
195 (MINCOST > MAXCOST) || |
|
196 (SUPPLY < SOURCES) || |
|
197 (TSOURCES > SOURCES) || |
|
198 (TSINKS > SINKS) || |
|
199 (HICOST < 0 || HICOST > 100) || |
|
200 (CAPACITATED < 0 || CAPACITATED > 100) || |
|
201 (MINCAP > MAXCAP)) |
|
202 return BAD_PARMS; |
|
203 |
|
204 |
|
205 /*** Do a little bit of setting up. */ |
|
206 |
|
207 set_random(seed); |
|
208 |
|
209 arc_count = 0; |
|
210 nodes_left = NODES - SINKS + TSINKS; |
|
211 |
|
212 if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES && |
|
213 (SOURCES-TSOURCES) == (SINKS-TSINKS) && |
|
214 SOURCES == SUPPLY) { |
|
215 create_assignment(parms); |
|
216 return arc_count; |
|
217 } |
|
218 |
|
219 (void)memset((void *)B, 0, sizeof(B));/* set supplies and demands to zero */ |
|
220 |
|
221 create_supply((NODE)SOURCES, (CAPACITY)SUPPLY); |
|
222 |
|
223 |
|
224 /*** Form most of the network skeleton. First, 60% of the transshipment |
|
225 *** nodes are divided evenly among the various sources; the remainder |
|
226 *** are chained onto the end of the chains belonging to random sources. |
|
227 ***/ |
|
228 |
|
229 for (i = 1; i <= SOURCES; i++) /* point SOURCES at themselves */ |
|
230 pred[i] = i; |
|
231 handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)(NODES - SINKS)); |
|
232 source = 1; |
|
233 for (i = NODES-SOURCES-SINKS; i > (4*(NODES-SOURCES-SINKS)+9)/10; i--) { |
|
234 node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle))); |
|
235 pred[node] = pred[source]; |
|
236 pred[source] = node; |
|
237 if (++source > SOURCES) |
|
238 source = 1; |
|
239 } |
|
240 for ( ; i > 0; --i) { |
|
241 node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle))); |
|
242 source = ng_random(1L, SOURCES); |
|
243 pred[node] = pred[source]; |
|
244 pred[source] = node; |
|
245 } |
|
246 free_index_list(handle); |
|
247 |
|
248 |
|
249 /*** For each source chain, hook it to an "appropriate" number of sinks, |
|
250 *** place capacities and costs on the skeleton edges, and then call |
|
251 *** pick_head to add a bunch of rubbish edges at each node on the chain. |
|
252 ***/ |
|
253 |
|
254 for (source = 1; source <= SOURCES; source++) { |
|
255 sort_count = 0; |
|
256 node = pred[source]; |
|
257 while (node != source) { |
|
258 sort_count++; |
|
259 head[sort_count] = node; |
|
260 node = tail[sort_count] = pred[node]; |
|
261 } |
|
262 if ((NODES-SOURCES-SINKS) == 0) |
|
263 sinks_per_source = SINKS/SOURCES + 1; |
|
264 else |
|
265 /* changing to handle overflows with large n; Mar 18 -- jc */ |
|
266 sinks_per_source = ((double) 2*sort_count*SINKS) / ((double) NODES-SOURCES-SINKS); |
|
267 sinks_per_source = MAX(2, MIN(sinks_per_source, SINKS)); |
|
268 sinks = (NODE*) malloc(sinks_per_source * sizeof(NODE)); |
|
269 handle = make_index_list((INDEX)(NODES - SINKS), (INDEX)(NODES - 1)); |
|
270 for (i = 0; i < sinks_per_source; i++) { |
|
271 sinks[i] = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle))); |
|
272 } |
|
273 if (source == SOURCES && index_size(handle) > 0) { |
|
274 sinks = (NODE*) realloc((void *)sinks, (sinks_per_source + index_size(handle)) * sizeof(NODE)); |
|
275 while (index_size(handle) > 0) { |
|
276 j = choose_index(handle, 1); |
|
277 if (B[j] == 0) |
|
278 sinks[sinks_per_source++] = j; |
|
279 } |
|
280 } |
|
281 free_index_list(handle); |
|
282 |
|
283 chain_length = sort_count; |
|
284 supply_per_sink = B[source-1] / sinks_per_source; |
|
285 k = pred[source]; |
|
286 for (i = 0; i < sinks_per_source; i++) { |
|
287 sort_count++; |
|
288 partial_supply = ng_random(1L, (long)supply_per_sink); |
|
289 j = ng_random(0L, (long)sinks_per_source - 1); |
|
290 tail[sort_count] = k; |
|
291 head[sort_count] = sinks[i] + 1; |
|
292 B[sinks[i]] -= partial_supply; |
|
293 B[sinks[j]] -= (supply_per_sink - partial_supply); |
|
294 k = source; |
|
295 for (j = ng_random(1L, (long)chain_length); j > 0; j--) |
|
296 k = pred[k]; |
|
297 } |
|
298 B[sinks[0]] -= (B[source-1] % sinks_per_source); |
|
299 free((void *)sinks); |
|
300 |
|
301 sort_skeleton(sort_count); |
|
302 tail[sort_count+1] = 0; |
|
303 for (i = 1; i <= sort_count; ) { |
|
304 handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES); |
|
305 remove_index(handle, (INDEX)tail[i]); |
|
306 it = tail[i]; |
|
307 while (it == tail[i]) { |
|
308 remove_index(handle, (INDEX)head[i]); |
|
309 cap = SUPPLY; |
|
310 if (ng_random(1L, 100L) <= CAPACITATED) |
|
311 cap = MAX(B[source-1], MINCAP); |
|
312 cost = MAXCOST; |
|
313 if (ng_random(1L, 100L) > HICOST) |
|
314 cost = ng_random(MINCOST, MAXCOST); |
|
315 SAVE_ARC(it,head[i],cost,cap); |
|
316 i++; |
|
317 } |
|
318 pick_head(parms, handle, it); |
|
319 free_index_list(handle); |
|
320 } |
|
321 } |
|
322 |
|
323 |
|
324 /*** Add more rubbish edges out of the transshipment sinks. */ |
|
325 |
|
326 for (i = NODES - SINKS + 1; i <= NODES - SINKS + TSINKS; i++) { |
|
327 handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES); |
|
328 remove_index(handle, (INDEX)i); |
|
329 pick_head(parms, handle, i); |
|
330 free_index_list(handle); |
|
331 } |
|
332 |
|
333 return arc_count; |
|
334 } |
|
335 |
|
336 |
|
337 PRIVATE void create_supply(sources, supply) |
|
338 NODE sources; |
|
339 CAPACITY supply; |
|
340 { |
|
341 CAPACITY supply_per_source = supply / sources; |
|
342 CAPACITY partial_supply; |
|
343 NODE i; |
|
344 |
|
345 for (i = 0; i < sources; i++) { |
|
346 B[i] += (partial_supply = ng_random(1L, (long)supply_per_source)); |
|
347 B[ng_random(0L, (long)(sources - 1))] += supply_per_source - partial_supply; |
|
348 } |
|
349 B[ng_random(0L, (long)(sources - 1))] += supply % sources; |
|
350 } |
|
351 |
|
352 |
|
353 PRIVATE void create_assignment(parms) |
|
354 long parms[]; |
|
355 { |
|
356 INDEX_LIST skeleton, handle; |
|
357 INDEX index; |
|
358 NODE source; |
|
359 |
|
360 for (source = 0; source < NODES/2; source++) |
|
361 B[source] = 1; |
|
362 for ( ; source < NODES; source++) |
|
363 B[source] = -1; |
|
364 |
|
365 skeleton = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES); |
|
366 for (source = 1; source <= NODES/2; source++) { |
|
367 index = choose_index(skeleton, (INDEX)ng_random(1L, (long)index_size(skeleton))); |
|
368 SAVE_ARC(source, index, ng_random(MINCOST, MAXCOST), 1); |
|
369 handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES); |
|
370 remove_index(handle, index); |
|
371 pick_head(parms, handle, source); |
|
372 free_index_list(handle); |
|
373 } |
|
374 free_index_list(skeleton); |
|
375 } |
|
376 |
|
377 |
|
378 PRIVATE void sort_skeleton(sort_count) /* Shell sort */ |
|
379 int sort_count; |
|
380 { |
|
381 int m,i,j,k; |
|
382 int temp; |
|
383 |
|
384 m = sort_count; |
|
385 while ((m /= 2) != 0) { |
|
386 k = sort_count - m; |
|
387 for (j = 1; j <= k; j++) { |
|
388 i = j; |
|
389 while (i >= 1 && tail[i] > tail[i+m]) { |
|
390 temp = tail[i]; |
|
391 tail[i] = tail[i+m]; |
|
392 tail[i+m] = temp; |
|
393 temp = head[i]; |
|
394 head[i] = head[i+m]; |
|
395 head[i+m] = temp; |
|
396 i -= m; |
|
397 } |
|
398 } |
|
399 } |
|
400 } |
|
401 |
|
402 |
|
403 PRIVATE void pick_head(parms, handle, desired_tail) |
|
404 long parms[]; |
|
405 INDEX_LIST handle; |
|
406 NODE desired_tail; |
|
407 { |
|
408 NODE non_sources = NODES - SOURCES + TSOURCES; |
|
409 |
|
410 /* changing Aug 29 -- jc |
|
411 ARC remaining_arcs = DENSITY - arc_count; |
|
412 */ |
|
413 int remaining_arcs = (int) DENSITY - (int) arc_count; |
|
414 |
|
415 INDEX index; |
|
416 int limit; |
|
417 long upper_bound; |
|
418 CAPACITY cap; |
|
419 |
|
420 /* changing Aug 29 -- jc |
|
421 */ |
|
422 nodes_left--; |
|
423 if ((2 * (int) nodes_left) >= (int) remaining_arcs) |
|
424 return; |
|
425 |
|
426 if ((remaining_arcs + non_sources - pseudo_size(handle) - 1) / (nodes_left + 1) >= non_sources - 1) { |
|
427 limit = non_sources; |
|
428 } else { |
|
429 upper_bound = 2 * (remaining_arcs / (nodes_left + 1) - 1); |
|
430 do { |
|
431 limit = ng_random(1L, upper_bound); |
|
432 if (nodes_left == 0) |
|
433 limit = remaining_arcs; |
|
434 /* changing to handle overflows with large n; Mar 18 -- jc */ |
|
435 } while ( ((double) nodes_left * (non_sources - 1)) < ((double) remaining_arcs - limit)); |
|
436 } |
|
437 |
|
438 for ( ; limit > 0; limit--) { |
|
439 index = choose_index(handle, (INDEX)ng_random(1L, (long)pseudo_size(handle))); |
|
440 cap = SUPPLY; |
|
441 if (ng_random(1L, 100L) <= CAPACITATED) |
|
442 cap = ng_random(MINCAP, MAXCAP); |
|
443 |
|
444 /* adding Aug 29 -- jc */ |
|
445 if ((1 <= index) && (index <= NODES)) { |
|
446 SAVE_ARC(desired_tail, index, ng_random(MINCOST, MAXCOST), cap); |
|
447 } |
|
448 |
|
449 } |
|
450 } |
|
451 |
|
452 |
|
453 /*** Print an appropriate error message and then exit with a nonzero code. */ |
|
454 |
|
455 PRIVATE void error_exit(rc) |
|
456 long rc; |
|
457 { |
|
458 switch (rc) { |
|
459 case BAD_SEED: |
|
460 fprintf(stderr, "NETGEN requires a positive random seed\n"); |
|
461 break; |
|
462 case TOO_BIG: |
|
463 fprintf(stderr, "Problem too large for generator\n"); |
|
464 break; |
|
465 case BAD_PARMS: |
|
466 fprintf(stderr, "Inconsistent parameter settings - check the input\n"); |
|
467 break; |
|
468 case ALLOCATION_FAILURE: |
|
469 fprintf(stderr, "Memory allocation failure\n"); |
|
470 break; |
|
471 default: |
|
472 fprintf(stderr, "Internal error\n"); |
|
473 break; |
|
474 } |
|
475 exit(1000 - (int)rc); |
|
476 } |
|
477 |
|
478 #ifdef DIMACS /* generates network on standard output */ |
|
479 |
|
480 #define READ(v) /* read one variable using scanf */ \ |
|
481 switch( scanf("%ld", &v) ) { \ |
|
482 case 1: \ |
|
483 break; \ |
|
484 default: \ |
|
485 exit(0); \ |
|
486 } |
|
487 |
|
488 int main() |
|
489 { |
|
490 long seed; |
|
491 long problem; |
|
492 long parms[PROBLEM_PARMS]; |
|
493 long arcs; |
|
494 int i; |
|
495 |
|
496 /*** Read problem parameters and generate networks */ |
|
497 |
|
498 while (1) { |
|
499 READ(seed); |
|
500 if (seed <= 0) exit(0); |
|
501 READ(problem); |
|
502 if (problem <= 0) exit(0); |
|
503 for (i = 0; i < PROBLEM_PARMS; i++) |
|
504 READ(parms[i]); |
|
505 printf("c NETGEN flow network generator (C version)\n"); |
|
506 printf("c Problem %2ld input parameters\n", problem); |
|
507 printf("c ---------------------------\n"); |
|
508 printf("c Random seed: %10ld\n", seed); |
|
509 printf("c Number of nodes: %10ld\n", NODES); |
|
510 printf("c Source nodes: %10ld\n", SOURCES); |
|
511 printf("c Sink nodes: %10ld\n", SINKS); |
|
512 printf("c Number of arcs: %10ld\n", DENSITY); |
|
513 printf("c Minimum arc cost: %10ld\n", MINCOST); |
|
514 printf("c Maximum arc cost: %10ld\n", MAXCOST); |
|
515 printf("c Total supply: %10ld\n", SUPPLY); |
|
516 printf("c Transshipment -\n"); |
|
517 printf("c Sources: %10ld\n", TSOURCES); |
|
518 printf("c Sinks: %10ld\n", TSINKS); |
|
519 printf("c Skeleton arcs -\n"); |
|
520 printf("c With max cost: %10ld%%\n", HICOST); |
|
521 printf("c Capacitated: %10ld%%\n", CAPACITATED); |
|
522 printf("c Minimum arc capacity: %10ld\n", MINCAP); |
|
523 printf("c Maximum arc capacity: %10ld\n", MAXCAP); |
|
524 |
|
525 if ((arcs = netgen(seed, parms)) < 0) |
|
526 error_exit(arcs); |
|
527 if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES && |
|
528 (SOURCES-TSOURCES) == (SINKS-TSINKS) && |
|
529 SOURCES == SUPPLY) { |
|
530 printf("c\n"); |
|
531 printf("c *** Assignment ***\n"); |
|
532 printf("c\n"); |
|
533 printf("p asn %ld %ld\n", NODES, arcs); |
|
534 for (i = 0; i < NODES; i++) { |
|
535 if (B[i] > 0) |
|
536 printf("n %ld\n", i + 1); |
|
537 } |
|
538 for (i = 0; i < arcs; i++) { |
|
539 printf("a %ld %ld %ld\n", FROM[i], TO[i], C[i]); |
|
540 } |
|
541 } else |
|
542 if (MINCOST == 1 && MAXCOST == 1) { |
|
543 printf("c\n"); |
|
544 printf("c *** Maximum flow ***\n"); |
|
545 printf("c\n"); |
|
546 printf("p max %ld %ld\n", NODES, arcs); |
|
547 for (i = 0; i < NODES; i++) { |
|
548 if (B[i] > 0) |
|
549 printf("n %ld s\n", i + 1); |
|
550 else |
|
551 if (B[i] < 0) |
|
552 printf("n %ld t\n", i + 1); |
|
553 } |
|
554 for (i = 0; i < arcs; i++) { |
|
555 printf("a %ld %ld %ld\n", FROM[i], TO[i], U[i]); |
|
556 } |
|
557 } else { |
|
558 printf("c\n"); |
|
559 printf("c *** Minimum cost flow ***\n"); |
|
560 printf("c\n"); |
|
561 printf("p min %ld %ld\n", NODES, arcs); |
|
562 for (i = 0; i < NODES; i++) { |
|
563 if (B[i] != 0) |
|
564 printf("n %ld %ld\n", i + 1, B[i]); |
|
565 } |
|
566 for (i = 0; i < arcs; i++) { |
|
567 printf("a %ld %ld %ld %ld %ld\n", FROM[i], TO[i], 0, U[i], C[i]); |
|
568 } |
|
569 } |
|
570 } |
|
571 return 0; |
|
572 } |
|
573 |
|
574 #endif |