Add a cost scaling min cost flow algorithm.
Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.
1 %!PS-Adobe-2.0 EPSF-2.0
2 %%Creator: LEMON, graphToEps()
3 %%CreationDate: Fri Oct 19 18:32:32 2007
4 %%BoundingBox: 0 0 596 842
5 %%DocumentPaperSizes: a4
7 /lb { setlinewidth setrgbcolor newpath moveto
8 4 2 roll 1 index 1 index curveto stroke } bind def
9 /l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
10 /c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
11 /sq { newpath 2 index 1 index add 2 index 2 index add moveto
12 2 index 1 index sub 2 index 2 index add lineto
13 2 index 1 index sub 2 index 2 index sub lineto
14 2 index 1 index add 2 index 2 index sub lineto
15 closepath pop pop pop} bind def
16 /di { newpath 2 index 1 index add 2 index moveto
17 2 index 2 index 2 index add lineto
18 2 index 1 index sub 2 index lineto
19 2 index 2 index 2 index sub lineto
20 closepath pop pop pop} bind def
21 /nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
22 setrgbcolor 1.1 div c fill
24 /nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
25 setrgbcolor 1.1 div sq fill
27 /ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
28 setrgbcolor 1.1 div di fill
30 /nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
31 newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
32 lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
33 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
34 5 index 5 index 5 index c fill
35 setrgbcolor 1.1 div c fill
38 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
39 newpath 5 index 5 index moveto
40 5 index 4 index 1 mul 1.5 mul add
41 5 index 5 index 3 sqrt 1.5 mul mul add
42 1 index 1 index lineto
43 1 index 1 index 7 index sub moveto
44 1 index 1 index lineto
45 exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
47 5 index 5 index 5 index c fill
48 setrgbcolor 1.1 div c fill
52 /lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
53 /arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
54 /w exch def /len exch def
55 newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
56 len w sub arrl sub dx dy lrl
58 dx arrl w add mul dy w 2 div arrw add mul sub
59 dy arrl w add mul dx w 2 div arrw add mul add rlineto
60 dx arrl w add mul neg dy w 2 div arrw add mul sub
61 dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
63 len w sub arrl sub neg dx dy lrl
64 closepath fill } bind def
65 /cshow { 2 index 2 index moveto dup stringwidth pop
66 neg 2 div fosi .35 mul neg rmoveto show pop pop} def
72 0.608112 -43.6081 translate
75 9 31 9.5 30.5 10 30 0 0 0 0.091217 lb
76 9 31 5.5 34.5 2 38 0 0 0 0.091217 lb
77 9 31 25.5 16 42 1 0 0 0 0.091217 lb
78 3 40 23 20.5 43 1 0 0 0 0.091217 lb
79 3 40 22.5 20.5 42 1 0 0 0 0.091217 lb
80 3 40 2.5 40.5 2 41 0 0 0 0.091217 lb
81 13 25 10.5 24.5 8 24 0 0 0 0.091217 lb
82 13 25 12 27 11 29 0 0 0 0.091217 lb
83 3 4 2.5 3 2 2 0 0 0 0.091217 lb
84 3 4 4.5 3 6 2 0 0 0 0.091217 lb
85 6 25 7 24.5 8 24 0 0 0 0.091217 lb
86 6 25 6 24.5 6 24 0 0 0 0.091217 lb
87 34 2 33.5 2 33 2 0 0 0 0.091217 lb
88 34 2 35 2 36 2 0 0 0 0.091217 lb
89 6 8 16 9 26 10 0 0 0 0.091217 lb
90 6 8 6 10.5 6 13 0 0 0 0.091217 lb
91 6 8 6 7.5 6 7 0 0 0 0.091217 lb
92 26 10 27.5 8.5 29 7 0 0 0 0.091217 lb
93 26 10 27.5 9 29 8 0 0 0 0.091217 lb
94 10 30 10.5 29.5 11 29 0 0 0 0.091217 lb
95 8 24 7 23.5 6 23 0 0 0 0.091217 lb
96 8 24 8 24.5 8 25 0 0 0 0.091217 lb
97 33 2 32.5 2 32 2 0 0 0 0.091217 lb
98 29 7 17.5 7 6 7 0 0 0 0.091217 lb
99 2 2 1.5 22 1 42 0 0 0 0.091217 lb
100 2 2 3.5 2 5 2 0 0 0 0.091217 lb
101 21 15 13.5 14.5 6 14 0 0 0 0.091217 lb
102 21 15 21 15.5 21 16 0 0 0 0.091217 lb
103 1 42 0.5 42.5 0 43 0 0 0 0.091217 lb
104 1 42 1.5 41.5 2 41 0 0 0 0.091217 lb
105 6 15 6 15.5 6 16 0 0 0 0.091217 lb
106 6 15 6 14.5 6 14 0 0 0 0.091217 lb
107 43 1 22 0.5 1 0 0 0 0 0.091217 lb
108 31 2 18.5 2 6 2 0 0 0 0.091217 lb
109 31 2 31.5 2 32 2 0 0 0 0.091217 lb
110 6 24 6 23.5 6 23 0 0 0 0.091217 lb
111 6 16 6 16.5 6 17 0 0 0 0.091217 lb
112 6 23 6 20 6 17 0 0 0 0.091217 lb
113 6 2 5.5 2 5 2 0 0 0 0.091217 lb
114 6 2 6 4.5 6 7 0 0 0 0.091217 lb
115 0 43 0.5 21.5 1 0 0 0 0 0.091217 lb
116 1 1 19.5 1.5 38 2 0 0 0 0.091217 lb
117 1 1 1 0.5 1 0 0 0 0 0.091217 lb
118 2 38 5.5 31.5 9 25 0 0 0 0.091217 lb
119 25 13 15.5 13 6 13 0 0 0 0.091217 lb
120 25 13 15.5 13.5 6 14 0 0 0 0.091217 lb
121 8 25 8.5 25 9 25 0 0 0 0.091217 lb
122 11 29 24.5 15.5 38 2 0 0 0 0.091217 lb
123 6 17 11.5 18 17 19 0 0 0 0.091217 lb
124 16 23 26.5 12.5 37 2 0 0 0 0.091217 lb
125 16 23 18.5 19.5 21 16 0 0 0 0.091217 lb
126 36 2 36.5 2 37 2 0 0 0 0.091217 lb
127 36 2 32.5 5 29 8 0 0 0 0.091217 lb
128 6 13 6 13.5 6 14 0 0 0 0.091217 lb
129 37 2 37.5 2 38 2 0 0 0 0.091217 lb
130 21 16 19 17.5 17 19 0 0 0 0.091217 lb
134 29 8 0.304556 1 1 1 nc
135 2 41 0.304556 1 1 1 nc
136 6 7 0.304556 1 1 1 nc
137 5 2 0.304556 1 1 1 nc
138 17 19 0.304556 1 1 1 nc
139 21 16 0.304556 1 1 1 nc
140 1 0 0.304556 1 1 1 nc
141 9 25 0.304556 1 1 1 nc
142 6 14 0.304556 1 1 1 nc
143 42 1 0.304556 1 1 1 nc
144 38 2 0.304556 1 1 1 nc
145 37 2 0.304556 1 1 1 nc
146 6 13 0.304556 1 1 1 nc
147 36 2 0.304556 1 1 1 nc
148 16 23 0.304556 1 1 1 nc
149 6 17 0.304556 1 1 1 nc
150 11 29 0.304556 1 1 1 nc
151 8 25 0.304556 1 1 1 nc
152 32 2 0.304556 1 1 1 nc
153 25 13 0.304556 1 1 1 nc
154 2 38 0.304556 1 1 1 nc
155 1 1 0.304556 1 1 1 nc
156 0 43 0.304556 1 1 1 nc
157 6 2 0.304556 1 1 1 nc
158 6 23 0.304556 1 1 1 nc
159 6 16 0.304556 1 1 1 nc
160 6 24 0.304556 1 1 1 nc
161 31 2 0.304556 1 1 1 nc
162 43 1 0.304556 1 1 1 nc
163 6 15 0.304556 1 1 1 nc
164 1 42 0.304556 1 1 1 nc
165 21 15 0.304556 1 1 1 nc
166 2 2 0.304556 1 1 1 nc
167 29 7 0.304556 1 1 1 nc
168 33 2 0.304556 1 1 1 nc
169 8 24 0.304556 1 1 1 nc
170 10 30 0.304556 1 1 1 nc
171 26 10 0.304556 1 1 1 nc
172 6 8 0.304556 1 1 1 nc
173 34 2 0.304556 1 1 1 nc
174 6 25 0.304556 1 1 1 nc
175 3 4 0.304556 1 1 1 nc
176 13 25 0.304556 1 1 1 nc
177 3 40 0.304556 1 1 1 nc
178 9 31 0.304556 1 1 1 nc