/*

  Maximum flow problem in Picat.

  From http://taha.ineg.uark.edu/maxflo.txt
  Taha "Introduction to Operations Research", Example 6.4-2)


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

*/

import sat.


main => go.

go =>
   N = 5,
   Start = 1,
   End = 5,
   C = [[0, 20, 30, 10,  0],
        [0,  0, 40,  0, 30],
        [0,  0,  0, 10, 20],
        [0,  0,  5,  0, 20],
        [0,  0,  0,  0,  0]],
   CC = [C[I,J] : I in 1..N, J in 1..N],
   Min = min(CC),
   Max = max(CC),
   
   X = new_array(N,N),
   XVars = vars(X),
   XVars :: Min..Max,

   OutFlow = new_list(N),
   InFlow = new_list(N),

   Total #= sum([X[Start,J] : J in 1..N, C[Start,J] > 0]),

   foreach(I in 1..N, J in 1..N) X[I,J] #>= 0, X[I,J] #=< C[I,J] end,
   foreach(I in 1..N) InFlow[I] #= sum([X[J,I] : J in 1..N, C[J,I] >0]) end,
   foreach(I in 1..N) OutFlow[I] #= sum([X[I,J] : J in 1..N, C[I,J]>0]) end,
   foreach(I in 1..N)
      if I != Start, I != End then
          OutFlow[I]-InFlow[I] #= 0
      end
   end,
   sum([X[I,Start] : I in 1..N, C[I,Start]>0]) #= 0 ,
   sum([X[End,J] : J in 1..N, C[End,J]>0]) #= 0,

   Vars = XVars ++ InFlow ++ OutFlow,
   solve([$max(Total)],Vars),

   writeln(total=Total),
   foreach(Row in X)
       foreach(R in Row) printf("%3d ",R) end, 
       nl
   end,
   writeln(inFlow=InFlow),
   writeln(outFlow=OutFlow),

   nl.