/*

  Maximum flow problem in Picat.

  From Winston "Operations Research", page 420f, 423f
  Sunco Oil example.

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.


main => go.

go =>

   Cap =  [2,3,3,4,2,1,100],
   Arcs = [[1, 2],
           [1, 3],
           [2, 3],
           [2, 4],
           [3, 5],
           [4, 5],
           [5, 1]],

   NumArcs = length(Cap),
   N = 5,
   Nodes = 1..N,

   Flow = new_array(N,N),
   Z #= Flow[N,1],

   foreach(I in Nodes, J in Nodes) Flow[I,J] #>= 0 end,
   foreach(I in 1..NumArcs) Flow[Arcs[I,1], Arcs[I,2]] #=< Cap[I] end,
   foreach(I in Nodes)
      sum([Flow[Arcs[K,1], Arcs[K,2]] : K in 1..NumArcs,Arcs[K,1] == I])
      #=
      sum([Flow[Arcs[K,1], Arcs[K,2]] : K in 1..NumArcs,Arcs[K,2] == I])
   end,

   solve([$max(Z)], Flow),

   writeln(z=Z),
   foreach(Row in Flow) writeln(Row) end,
   nl.