//JOB(ERCC07,STEPHENS,T=200,L=10000)
//OPTIONS(QUOTES,OPT)
//ALGOL
'COMMENT'
                         ***************
                         *             *
                         *   ALGG045   *
                         *             *
                         ***************
;

 'BEGIN'
'COMMENT' G4628T;
'INTEGER' COUNT;
'BEGIN' 'INTEGER' I,J,K,M,N,MIN,L,FLOWH,F,X;
COUNT:=0;
      M:=READ;N:=READ;
'BEGIN' 'INTEGER' 'ARRAY' ZERO,BOOL,U[1:N-1,1:M-1],C,WGHT[1:N,1:M],
            COL[1:N,1:2],ROW[1:2,1:M];
      'BOOLEAN' 'ARRAY' NLROW[1:N-1],NLCOL[1:M-1];'BOOLEAN' MLAB;
    WRITETEXT('(''('C')'COST'('S')'MATRIX'('S')'IS')');
      'FOR' I:=1 'STEP' 1 'UNTIL' N 'DO' 'BEGIN' WRITETEXT('(''('C')'')'
);
      'FOR' J:=1 'STEP' 1 'UNTIL' M 'DO'

      'BEGIN' C[I,J]:=READ;WGHT[I,J]:=0;PRINT(C[I,J],2,0);'END';
  'END';
      'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO'
      'BEGIN' BOOL[I,J]:=0;ZERO[I,J]:=0;U[I,J]:=0;'END';
      K:=0;MIN:=0;
      'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO' K:=K+C[I,M];
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' MIN:=MIN+C[N,J];
      'IF' K\=MIN'THEN' 'BEGIN' WRITETEXT('(''('C')'NO SOLN')'); 'GOTO'
NOSOLN;'END';
'COMMENT'  GETTING STARTED  IE.FIND STARTING WEIGHTS AND ZERO MATRIX;
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'BEGIN' MIN:=C[I,1]; 'FOR' J:=1 'STEP' 1 'UNTIL' M-2 'DO'
      'IF' MIN>C[I,J+1] 'THEN' MIN:=C[I,J+1];
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO'
      'IF' C[I,J]=MIN 'THEN' BOOL[I,J]:=1;
      WGHT[I,M]:=-MIN;
'END';
'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO'
'BEGIN' 'FOR' I:=1 'STEP' 1 'UNTIL' N-1'DO'
      'IF' BOOL[I,J]=1 'THEN' 'GOTO' FINISH;
      WGHT[1,J]:=C[1,J]+WGHT[1,M];
      MIN:=WGHT[1,J];
      'FOR' I:=2 'STEP' 1 'UNTIL' N-1 'DO'
      'BEGIN' WGHT[I,J]:=C[I,J]+WGHT[I,M];
            'IF' MIN>WGHT[I,J] 'THEN' MIN:=WGHT[I,J];
      'END';
      'FOR' I:=2 'STEP' 1 'UNTIL' N-1 'DO'
      'BEGIN' WGHT[I,J]:=WGHT[I,J]-MIN;
            'IF' WGHT[I,J]=0 'THEN' BOOL[I,J]:=1;
      'END';
      WGHT[N,J]:=-MIN;
FINISH:
'END';
'COMMENT' DETERMINATION OF INITIAL ALLOCATIONS;
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'BEGIN' 'IF' C[I,M]=0 'THEN' 'GOTO' LOOP1;
      'FOR' J:= 1 'STEP' 1 'UNTIL' M-1 'DO'
      'IF' BOOL[I,J]=1 'THEN'
      'BEGIN' 'IF' C[N,J]=0 'THEN' 'GOTO' LOOP2;
           X:='IF' U[I,J]>C[N,J] 'THEN' C[N,J] 'ELSE' U[I,J];
            'IF' C[I,M]>X 'THEN'
            'BEGIN' ZERO[I,J]:=X;C[I,M]:=C[I,M]-X;
                  C[N,J]:=C[N,J]-X;
            'END'
            'ELSE' 'BEGIN' ZERO[I,J]:=C[I,M];
                      C[N,J]:=C[N,J]-C[I,M];C[I,M]:=0;'GOTO' LOO
P1;
                  'END';
'END';
LOOP2:
LOOP1:
'END';
'COMMENT' STARTING LABELLING PROCESS,FIRST ROWS WITH SURPLUS;STLAB:
COUNT:=COUNT + 1;
'IF' COUNT > 100 'THEN' 'GOTO' NOSOLN;
'FOR' I:=1 'STEP' 1 'UNTIL' N 'DO' COL[I,1]:=COL[I,2]:=0;
'FOR' J:=1 'STEP' 1 'UNTIL' M 'DO' ROW[1,J]:=ROW[2,J]:=0;
WRITETEXT('(''('CC')'C[I,J],WGHT[I,J]')');
'FOR' I:=1 'STEP' 1 'UNTIL' N 'DO'
'BEGIN' WRITETEXT('(''('C')'')');
      'FOR' J:=1 'STEP' 1 'UNTIL' M 'DO' PRINT(C[I,J],2,0);
      'FOR' J:=1 'STEP' 1 'UNTIL' M 'DO' PRINT(WGHT[I,J],2,0);
'END';
WRITETEXT('(''('C')'BOOL[I,J],ZERO[I,J]')');
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'BEGIN' WRITETEXT('(''('C')'')');
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' PRINT(BOOL[I,J],2,0);
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' PRINT(ZERO[I,J],2,0);
'END';
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' WGHT[I,J]:=0;
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO' NLROW[I]:='FALSE';
'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' NLCOL[J]:='FALSE';MLAB:='FALSE';
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'IF' C[I,M]>0 'THEN' 'BEGIN' COL[I,1]:=C[I,M];COL[I,2]:=0;
            NLROW[I]:='TRUE';MLAB:='TRUE';'END';
'COMMENT'  LABELLING COLUMNS AND TEST FOR NO MORE LABELLING;
LABCOL:'IF' 'NOT' MLAB 'THEN' 'GOTO' NOBREAK;
'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' NLCOL[J]:='FALSE';
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'BEGIN' 'IF' COL[I,1]=0 'OR' 'NOT' NLROW[I] 'THEN' 'GOTO' JUMP;
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO'
      'IF' BOOL[I,J]=1 'AND' ROW[1,J]=0 'THEN'
      'BEGIN' ROW[1,J]:=COL[I,1];ROW[2,J]:=I;
            'IF' C[N,J]>0 'THEN' 'BEGIN' WRITETEXT('(''('C')'BRTHR')')
;PRINT(J,2,0);
             'GOTO' BREAKTHROUGH;'END';MLAB:='TRUE';NLCOL[J]:='TRUE';
      'END';  JUMP:
'END';
'COMMENT' TEST FOR NO MORE LABELLING;
 'IF' 'NOT' MLAB 'THEN' 'GOTO' NOBREAK;
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO' NLROW[I]:='FALSE'; MLAB:='FALSE';
'COMMENT' LABELLING ROWS;
'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO'
'BEGIN' 'IF' 'NOT' NLCOL[J]  'THEN' 'GOTO' AGAIN;
      'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
      'BEGIN' 'IF' COL[I,1]>0 'THEN' 'GOTO' AG2;
      'IF' BOOL[I,J]=1 'AND' ZERO[I,J]>0 'THEN'
      'BEGIN' NLROW[I]:='TRUE';MLAB:='TRUE';
            COL[I,1]:='IF' ZERO[I,J]>ROW[1,J] 'THEN' ROW[1,J]
             'ELSE' ZERO[I,J];
            COL[I,2]:=J;
      'END';AG2:
'END';
      AGAIN:
'END';
WRITETEXT('(''('C')'COL[I,J]')');
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO' 'BEGIN'
      PRINT(COL[I,1],2,0); PRINT(COL[I,2],2,0);
         'END';
WRITETEXT('(''('C')'ROW[I,J]')');
'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' 'BEGIN'
      PRINT(ROW[1,J],2,0); PRINT(COL[2,J],2,0);
          'END';
'GOTO' LABCOL;
'COMMENT' %NO BREAKTHROUGH% ACHIEVED;NOBREAK:
WRITETEXT('(''('C')'NOBREAK')');
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'BEGIN' 'IF' COL[I,1]=0 'THEN' 'GOTO' NEXT;
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO'
      'BEGIN' 'IF' ROW[1 ,J]\=0'THEN' 'GOTO' NEXT1 ;
            WGHT[I,J]:=C[I,J]+WGHT[I,M]+WGHT[N,J];NEXT1:
'END';NEXT:
'END';
'COMMENT' FIND %K%;
K:=5*10**5;
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'BEGIN' 'IF' COL[I,1]=0 'THEN' 'GOTO' NEXT2 ;
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO'
      'BEGIN' 'IF' ROW[1,J]\=0'THEN' 'GOTO' NEXT3;
            'IF' WGHT[I,J]<K 'THEN' K:=WGHT[I,J];
      NEXT3:
'END';NEXT2:
'END';
'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' 'IF' ROW[1,J]>0 'THEN' WGHT[N,J
]:=W
GHT[N,J]+K;
'COMMENT' ADDING CIRCLES AND REMOVING CIRCLES;
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'BEGIN' 'IF' COL[I,1]=0 'THEN' 'GOTO' RTURN;
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO'
      'BEGIN' 'IF' ROW[1,J]>0 'THEN' 'FOR' L:=1 'STEP' 1 'UNTIL' N-1 '
DO
'
            'IF' BOOL[L,J]=1 'AND' COL[L,1]>0 'THEN' BOOL[L,J]:=0;
            'IF' WGHT[I,J]=K 'THEN' BOOL[I,J]:=1;
      'END';WGHT[I,M]:=WGHT[I,M]-K;RTURN:
'END';
'GOTO' STLAB;
'COMMENT' %BREAKTHROUGH% ACHIEVED;BREAKTHROUGH:
STOP; 'COMMENT' ADDED BY PDS PROG LOOPING;
 X:='IF' U[I,J]>C[N,J] 'THEN' C[N,J] 'ELSE' U[I,J];
FLOWH:= 'IF' X>ROW[1,J] 'THEN' ROW[1,J] 'ELSE' X;
 C[N,J]:=C[N,J]-FLOWH;REPEAT:
ZERO[I,J]:=ZERO[I,J]+FLOWH;J:=COL[I,2];
'IF' J=0 'THEN' 'GOTO' RPEAT;ZERO[I,J]:=ZERO[I,J]-FLOWH;
I:=ROW[2,J];'GOTO' REPEAT; RPEAT:
C[I,M]:=C[I,M]-FLOWH;'GOTO' TESTOP;
TESTOP:
'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' 'IF' C[N,J]>0 'THEN' 'GOTO' STLAB
;
WRITETEXT('(''('CC')'SOLN%IS')');
'FOR' I:=1 'STEP' 1 'UNTIL' N-1 'DO'
'BEGIN' WRITETEXT('(''('C')'')');
      'FOR' J:=1 'STEP' 1 'UNTIL' M-1 'DO' PRINT(ZERO[I,J],2,0);
'END';
NOSOLN:
'END';
 'END';
'END'

//RUN
7;5;5;3;7;3;8;5;3;
5;6;12;5;7;11;4;
2;8;3;4;8;2;2;
9;6;10;5;10;9;8;
3;3;6;2;1;2;0;