C TP1 0000 C *TEST PROGRAM #1* (DATA INPUT FROM CARDS) TP1 0001 C THIS IS THE FIRST OF TWO PROGRAMS FOR THE TESTING OF THE TP1 0002 C SUBROUTINE 'LOCATE'. ALL IT DOES IS TO READ THE DATA NVPT, TP1 0003 C NFPT, VWT AND VFWT FROM CARDS, CALL 'LOCATE', AND PRINT THE TP1 0004 C SOLUTION POST. TP1 0005 C IT FIRST READS AN INTEGER NPRLM FROM A CARD, USING TP1 0006 C FORMAT(I3), WHERE NPRLM IS THE NUMBER OF PROBLEMS TO BE TP1 0007 C TESTED IN A SINGLE RUN. THEN, FOR EACH PROBLEM TESTED, TP1 0008 C A SET OF 1+2*NVPT DATA CARDS WILL BE READ. THE FORMAT TP1 0009 C AND SETUP OF THESE CARDS SHOULD BE CLEAR FROM THE READ TP1 0010 C STATEMANTS AT STATEMENT LABEL 2, IN LOOP 7 AND LOOP 10. TP1 0011 C TP1 0012 INTEGER VWT(30,30),VFWT(30,60),POST(30) TP1 0013 C TP1 0014 C FOR EXPLANATION OF THESE VECTORS, SEE SUBROUTINE 'LOCATE'. TP1 0015 C TP1 0016 READ(5,1) NPRLM TP1 0017 1 FORMAT(I3) TP1 0018 NP=1 TP1 0019 2 READ(5,3) NVPT,NFPT TP1 0020 3 FORMAT(2I3) TP1 0021 WRITE(6,4) NP,NVPT,NFPT TP1 0022 4 FORMAT(1H1/////14H TEST PROBLEM ,I3//11H NUMBER OF , TP1 0023 119HVARIABLE POINTS IS ,I3,24H; NUMBER OF FIXED POI, TP1 0024 17HNTS IS ,I2) TP1 0025 WRITE(6,5) TP1 0026 5 FORMAT(20H0WEIGHT MATRIX VWT :/) TP1 0027 DO 7 I=1,NVPT TP1 0028 READ(5,6) (VWT(I,J),J=1,NVPT) TP1 0029 6 FORMAT(25I3) TP1 0030 7 WRITE(6,8) (VWT(I,J),J=1,NVPT) TP1 0031 8 FORMAT(5X,22(I3,1X)/13X,20(I3,1X)/13X,20(I3,1X)) TP1 0032 WRITE(6,9) TP1 0033 9 FORMAT(21H0WEIGHT MATRIX VFWT :/) TP1 0034 DO 10 I=1,NVPT TP1 0035 READ(5,6) (VFWT(I,J),J=1,NFPT) TP1 0036 10 WRITE(6,8) (VFWT(I,J),J=1,NFPT) TP1 0037 CALL LOCATE(NVPT,NFPT,VWT,VFWT,POST) TP1 0038 WRITE(6,11) (POST(I),I=1,NVPT) TP1 0039 11 FORMAT(38H-OPTIMAL LOCATIONS OF VARIABLE POINTS , TP1 0040 142HCOINCIDE WITH THE FOLLOWING FIXED POINTS ://3X, TP1 0041 122(I3,1X)/3X,20(I3,1X)) TP1 0042 C TP1 0043 C CHECK WHETHER THERE IS MORE TEST PROBLEM TP1 0044 NP=NP+1 TP1 0045 IF(NP.LE.NPRLM) GO TO 2 TP1 0046 STOP TP1 0047 END TP1 0048 C TP2 0000 C *TEST PROGRAM #2* (DATA GENERATED RANDOMLY) TP2 0001 C THIS IS THE SECOND OF THE TWO MAIN PROGRAMS FOR TESTING TP2 0002 C THE SUBROUTINE 'LOCATE'. IT TESTS DATA GENERATED RANDOMLY TP2 0003 C BY A SUBROUTINE CALLED RANDU. IT FIRST READS AN INTEGER TP2 0004 C NPRLM FROM A CARD, USING FORMAT(I3), WHERE NPRLM IS THE TP2 0005 C NUMBER OF PROBLEMS TO BE TESTED IN A SINGLE RUN. FOR EACH TP2 0006 C PROBLEM TESTED, THE USER PROVIDES ONLY A SINGLE CARD TO BE TP2 0007 C READ BY THE FOLLOWING STATEMENTS: TP2 0008 C TP2 0009 C 2 READ(5,3)NVPT,NFPT,NCHECK,MVWT,MVFWT,RANGE TP2 0010 C TP2 0011 C 3 FORMAT(5I3,F6.2) TP2 0012 C TP2 0013 C WHERE TP2 0014 C NVPT - NUMBER OF VARIABLE POINTS. TP2 0015 C NFPT - NUMBER OF FIXED POINTS. TP2 0016 C NCHECK - NUMBER OF SETS OF VARIABLE-POINT LOCATIONS TP2 0017 C GENERATED FOR CHECKING THE OPTIMALITY OF THE TP2 0018 C OBTAINED SOLUTION. TP2 0019 C MVWT - UPPER BOUND ON THE WEIGHTS (<1000) BETWEEN THE TP2 0020 C VARIABLE POINTS. TP2 0021 C MVFWT - UPPER BOUND ON THE WEIGHTS (<1000) BETWEEN THE TP2 0022 C FIXED AND VARIABLE POINTS. TP2 0023 C RANGE - UPPER BOUND ON THE RANGE OF LOCATIONS GENERATED. TP2 0024 C TP2 0025 C USING THESE INPUT DATA, THIS PROGRAM FIRST RANDOMLY GENERATES TP2 0026 C A SET OF FIXED-POINTS LOCATIONS. IT THEN GENERATES RANDOMLY TP2 0027 C NCHECK SETS OF VARIABLE-POINT LOCATIONS AND COMPARES THEM TP2 0028 C WITH THE OPTIMAL LOCATIONS OBTAINED BY 'LOCATE'. TP2 0029 C THIS MAIN PROGRAM INCLUDES THREE OTHER SUBROUTINES: TP2 0030 C RANDU, CHECK AND SUM. TP2 0031 C TP2 0032 C TP2 0033 INTEGER VWT(30,30),VFWT(30,60),POST(30) TP2 0034 C TP2 0035 C FOR EXPLANATION OF THESE VECTORS, SEE SUBROUTINE 'LOCATE'. TP2 0036 C TP2 0037 READ(5,1) NPRLM TP2 0038 1 FORMAT(I3) TP2 0039 IY=2*NPRLM+1 TP2 0040 NP=1 TP2 0041 2 READ(5,3) NVPT,NFPT,NCHECK,MVWT,MVFWT,RANGE TP2 0042 3 FORMAT(5I3,F6.2) TP2 0043 WRITE(6,4) NP,NVPT,NFPT TP2 0044 4 FORMAT(1H1/////14H TEST PROBLEM ,I3//11H NUMBER OF , TP2 0045 119HVARIABLE POINTS IS ,I3,24H; NUMBER OF FIXED POI, TP2 0046 17HNTS IS ,I2) TP2 0047 WRITE(6,5) MVWT TP2 0048 5 FORMAT(35H0WEIGHT MATRIX VWT (UPPER BOUND IS ,I3,2H):/) TP2 0049 C TP2 0050 C GENERATE MATRIX VWT CONTAINING WEIGHTS BETWEEN VARIABLE TP2 0051 C POINTS. TP2 0052 DO 9 I=1,NVPT TP2 0053 DO 6 J=I,NVPT TP2 0054 IX=IY TP2 0055 CALL RANDU(IX,IY,YFL) TP2 0056 TEMP=FLOAT(MVWT)*YFL TP2 0057 VWT(I,J)=INT(TEMP) TP2 0058 VWT(J,I)=VWT(I,J) TP2 0059 IF (I.EQ.J) VWT(I,J)=0 TP2 0060 6 CONTINUE TP2 0061 WRITE(6,7) (VWT(I,J),J=1,NVPT) TP2 0062 7 FORMAT(5X,22(I3,1X)/13X,20(I3,1X)/13X,20(I3,1X)) TP2 0063 C TP2 0064 C GENERATE MATRIX VFWT CONTAINING WEIGHTS BETWEEN VARIABLE AND TP2 0065 C FIXED POINTS. TP2 0066 DO 8 J=1,NFPT TP2 0067 IX=IY TP2 0068 CALL RANDU(IX,IY,YFL) TP2 0069 TEMP=FLOAT(MVFWT)*YFL TP2 0070 VFWT(I,J)=INT(TEMP) TP2 0071 8 CONTINUE TP2 0072 9 CONTINUE TP2 0073 WRITE(6,10) MVFWT TP2 0074 10 FORMAT(36H0WEIGHT MATRIX VFWT (UPPER BOUND IS ,I3, TP2 0075 12H):/) TP2 0076 DO 11 I=1,NVPT TP2 0077 11 WRITE(6,7) (VFWT(I,J),J=1,NFPT) TP2 0078 C TP2 0079 C FIND AN OPTIMAL SOLUTION BY CALLING 'LOCATE'. TP2 0080 CALL LOCATE(NVPT,NFPT,VWT,VFWT,POST) TP2 0081 WRITE(6,12) (POST(I),I=1,NVPT) TP2 0082 12 FORMAT(38H-OPTIMAL LOCATIONS OF VARIABLE POINTS , TP2 0083 142HCOINCIDE WITH THE FOLLOWING FIXED POINTS ://3X, TP2 0084 122(I3,1X)/3X,20(I3,1X)) TP2 0085 C TP2 0086 C TO TEST THE OPTIMALTY OF THE SOLUTION OBTAINED BY 'LOCATE', TP2 0087 C THE SUBROUTINE CHECK GENERATES NCHECK SETS OF VARIABLE- TP2 0088 C POINT LOCATIONS IN THE RANGE (0,RANGE) FOR COMPARISON. TP2 0089 CALL CHECK(NVPT,NFPT,VWT,VFWT,POST,NCHECK,RANGE) TP2 0090 NP=NP+1 TP2 0091 IF(NP.LE.NPRLM) GO TO 2 TP2 0092 STOP TP2 0093 END TP2 0094 SUBROUTINE RANDU(IX,IY,YFL) TP2 0095 C C THIS GENERATOR GENERATES A NUMBER RANDOMLY AND UNIFORMLY C IN (0,1). SEE MACLAREN AND MARSALIA, J. ACM, VOL. 12, C PP.83-89, AND IBM SCIENTIFIC SUBROUTINE PACKAGE. C IY=IX*65539 IF (IY) 1,2,2 1 IY=IY+2147483647+1 2 YFL=IY YFL=YFL*0.4656613E-9 RETURN END SUBROUTINE CHECK(NVPT,NFPT,VWT,VFWT,POST,NCHECK,RANGE) TP2 0108 C C THIS SUBROUTINE FIRST RANDOMLY GENERATES A SET OF FIXED- C POINT LOCATIONS. IT THEN GENERATES RANDOMLY NCHECK SETS OF C VARIABLE-POINT LOCATIONS AND COMPARES THEM WITH THE C OPTIMAL LOCATIONS OBTAINED BY THE ALGORITHM. C INTEGER VWT(30,1),VFWT(30,1),POST(1) DIMENSION VPLOC(30),FPLOC(60) C C VPLOC - VARIABLE-POINT LOCATIONS. C FPLOC - FIXED-POINT LOCATIONS. C THE MEANINGS OF THE OTHER VARIABLES ARE GIVEN IN THE TEST C PROGRAM #2. C C GENERATE FIXED-POINT LOCATIONS. C IY=NCHECK*2+1 FPLOC(1)=0. DO 1 I=2,NFPT IX=IY CALL RANDU(IX,IY,YFL) FPLOC(I)=YFL*RANGE 1 CONTINUE N1=NFPT-1 DO 3 I=2,N1 I1=I+1 DO 2 J=I1,NFPT IF (FPLOC(I).LE.FPLOC(J)) GO TO 2 T=FPLOC(I) FPLOC(I)=FPLOC(J) FPLOC(J)=T 2 CONTINUE 3 CONTINUE T=FPLOC(NFPT) WRITE(6,4) RANGE,T 4 FORMAT(14H0RANDOM CHECK://3X,13HFIXED-POINT , 150H LOCATIONS ARE GENERATED RANDOMLY IN THE RANGE (0, 14H.00,,F6.2,1H)/3X,29HVARIABLE-POINT LOCATIONS ARE , 138HGENERATED RANDOMLY IN THE RANGE (0.00,,F6.2,1H)// 14X,26HFIXED-POINT LOCATIONS ARE:) WRITE(6,5) (FPLOC(I),I=1,NFPT) 5 FORMAT(7X,12F7.2) C C GENERATE VARIABLE-POINT LOCATIONS AND EVALUATE THE C WEIGHTED SUM OF DISTANCES. DO 6 I=1,NVPT J=POST(I) VPLOC(I)=FPLOC(J) 6 CONTINUE WRITE(6,7) 7 FORMAT(42H0 OPTIMAL VARIABLE-POINT LOCATIONS ARE:) WRITE(6,5) (VPLOC(I),I=1,NVPT) S=SUM(NVPT,NFPT,VWT,VFWT,VPLOC,FPLOC) WRITE(6,8) S 8 FORMAT(8X,29HWEIGHTED SUM OF DISTANCES IS:,3X,E11.3) DO 11 I=1,NCHECK DO 9 J=1,NVPT IX=IY CALL RANDU(IX,IY,YFL) VPLOC(J)=YFL*T 9 CONTINUE WRITE(6,10) I 10 FORMAT(15H0 CHECK #(,I3,2H):,5X,11HVARIABLE-PO, 1 18HINT LOCATIONS ARE:) WRITE(6,5) (VPLOC(J),J=1,NVPT) S=SUM(NVPT,NFPT,VWT,VFWT,VPLOC,FPLOC) WRITE(6,8) S 11 CONTINUE RETURN END FUNCTION SUM(NVPT,NFPT,VWT,VFWT,VPLOC,FPLOC) TP2 0179 C C THIS SUBROUTINE CALCULATES THE WEIGHTED SUM OF DISTANCES C BETWEEN ALL THE VARIABLE POINTS AND FIXED POINTS. C THE MEANINGS OF THE INPUT PARAMETERS ARE EXPLAINED IN THE C SUBROUTINE 'CHECK' AND TEST PROGRAM #2. C INTEGER VWT(30,1),VFWT(30,1) DIMENSION VPLOC(1),FPLOC(1) SUM=0. DO 3 I=1,NVPT DO 1 J=1,I IF (I.NE.J) SUM=SUM+FLOAT(VWT(I,J)) 1 *ABS(VPLOC(I)-VPLOC(J)) 1 CONTINUE DO 2 J=1,NFPT SUM=SUM+FLOAT(VFWT(I,J))*ABS(VPLOC(I)-FPLOC(J)) 2 CONTINUE 3 CONTINUE RETURN END SUBROUTINE LOCATE(NVPT,NFPT,VWT,VFWT,POST) LOC 0000 C C THIS SUBROUTINE SOLVES THE FOLLOWING ONE-DIMENSIONAL C MULTIFACILITY LOCATION PROBLEM USING AN ALGORITHM DESIGNED C BY PICARD, RATLIFF (SEE OPERATIONS RESEARCH 26 (1978), C PP.422-433) AND CHEUNG. C " GIVEN NFPT FIXED POINTS ON A LINE, DETERMINE THE C LOCATIONS OF NVPT VARIABLE POINTS SUCH THAT A WEIGHTED C SUM OF THE DISTANCES BETWEEN THE POINTS IS MINIMUM." C OUR ALGORITHM TRANSFORMS THE LOCATION PROBLEM TO A SEQUENCE C OF MINIMUM-CUT PROBLEMS. A FORTRAN CODE (THE SUBROUTINE C NETFLO IN "COMBINATORIAL ALGORITHMS", WRITTEN BY NIJENHUIS C AND WILF) OF DINIC'S ALGORITHM IS USED TO FIND THE MINIMUM C CUTS. C TO APPLY THE SUBROUTINE 'LOCATE', THE FIXED POINTS SHOULD C BE SUBSCRIPTED ON THE LINE IN INCREASING ORDER OF THEIR C LOCATIONS. THEIR EXACT LOCATIONS ARE NOT REQUIRED. C INTEGER COL,SOURCE,SUM INTEGER POST(1),CVPT(32),CUT(32),ENDPT(4,930) INTEGER VWT(30,1),VFWT(30,1) C C ON INPUT C NVPT NUMBER OF VARIABLE POINTS. C NFPT NUMBER OF FIXED POINTS. C VWT A SQUARE MATRIX WHOSE UPPER TRIANGULAR PART C CONTAINS THE WEIGHTS BETWEEN THE VARIABLE POINTS. C THE WEIGHTS MUST BE NON-NEGATIVE INTEGERS. C VFWT WEIGHTS BETWEEN THE VARIABLE AND FIXED POINTS. C THE WEIGHTS MUST BE NON-NEGATIVE INTEGERS. C ON OUTPUT C POST A VECTOR INDICATING THE OPTIMAL LOCATIONS OF THE C VARIABLE POINTS. VARIABLE POINT I WILL COINCIDE C WITH THE FIXED POINT WHOSE POSITION IS POST(I). C FOR WORKING STORAGE C (IN THE FOLLOWING, MNVP MEANS 'THE MAXIMUM NUMBER OF C VARIABLE POINTS'.) C CVPT A VECTOR OF LENGTH MNVP+2. IT REPRESENTS THE C VARIABLE POINTS WHICH PARTICIPATE IN THE CURRENT C ITERATION. THE VARIABLE POINT CVPT(I) IS THE C NODE I OF THE CURRENT NETWORK. C ENDPT A MATRIX OF DIMENSION 4 X E, WHERE E=MNVP* C *(MNVP+1). EACH ARC CORRESPONDS TO A COLUMN OF C ENDPT, WHOSE 4 ROWS DENOTE THE INITIAL VERTEX, C THE TERMINAL VERTEX, THE CAPACITY AND MAXIMUM C FLOW OF THAT ARC RESPECTIVELY. C CUT A VECTOR OF LENGTH MNVP+2. FOR A MIN-CUT, C CUT(I)=1 MEANS NODE I IS ASSOCIATED WITH THE C SOURCE, AND CUT(I)=0 MEANS NODE I IS ASSOCIATED C WITH THE SINK. C IF (NVPT.EQ.1) GO TO 13 C C INITIALIZE ENDPT FOR THE FIRST ITERATION. SOURCE=NVPT+1 COL=0 DO 6 I=1,NVPT CVPT(I)=I POST(I)=0 DO 5 J=1,NVPT COL=COL+1 ENDPT(1,COL)=I ENDPT(2,COL)=J ENDPT(4,COL)=0 IF (I-J) 1,2,4 1 ENDPT(3,COL)=VWT(I,J) GO TO 5 2 ENDPT(1,COL)=SOURCE SUM=0 DO 3 K=1,NFPT SUM=SUM+VFWT(I,K) 3 CONTINUE ENDPT(3,COL)=SUM GO TO 5 4 ENDPT(3,COL)=VWT(J,I) 5 CONTINUE 6 CONTINUE NN=NVPT C C ITERATIONS DO 12 ITER=1,NFPT NNODE=NN+2 DO 7 I=1,NN COL=COL+1 ENDPT(1,COL)=I ENDPT(2,COL)=NNODE L=CVPT(I) ENDPT(3,COL)=2*VFWT(L,ITER) ENDPT(4,COL)=0 7 CONTINUE C C SOLVE A MIN-CUT PROBLEM BY DINIC'S ALGORITHM. CALL NETFLO(NNODE,COL,ENDPT,SOURCE,NNODE,CUT) C C UPDATE POST AND INITIALIZE CVPT FOR THE NEXT ITERATION. N2=NN NN=0 DO 9 I=1,N2 IF (CUT(I).EQ.1) GO TO 8 L=CVPT(I) POST(L)=ITER GO TO 9 8 NN=NN+1 CVPT(NN)=CVPT(I) 9 CONTINUE C C NN IS THE NUMBER OF VARIABLE POINTS IN THE NEXT ITERATION. IF (NN.EQ.0) RETURN C C INITIALIZE ENDPT FOR THE NEXT ITERATION. SOURCE=NN+1 COL=0 IL=0 DO 11 I=1,N2 IF(CUT(I).EQ.0) GO TO 11 IL=IL+1 JL=0 DO 10 J=1,N2 IF(CUT(J).EQ.0) GO TO 10 COL=COL+1 JL=JL+1 ENDPT(1,COL)=IL IF(I.EQ.J) ENDPT(1,COL)=SOURCE ENDPT(2,COL)=JL L=(I-1)*N2+J ENDPT(3,COL)=ENDPT(3,L)-ENDPT(4,L) ENDPT(4,COL)=0 10 CONTINUE 11 CONTINUE 12 CONTINUE RETURN C C IN CASE THE NUMBER OF VARIABLE POINTS IS 1, OUR PROBLEM IS C THE SAME AS THE 1-MEDIAN LOCATION PROBLEM. OUR ALGORITHM C IS ALSO EQUIVALENT TO THE FOLLOWING WELL-KNOWN SIMPLE C PROCESS FOR SOLVING 1-MEDIAN LOCATION PROBLEMS. 13 SUM=-VFWT(1,1) DO 14 I=2,NFPT SUM=SUM+VFWT(1,I) 14 CONTINUE I=1 15 IF (SUM.LE.0) GO TO 16 I=I+1 SUM=SUM-VFWT(1,I)*2 GO TO 15 16 POST(1)=I RETURN END SUBROUTINE NETFLO(N,E,ENDPT,SOURCE,SINK,CUT) NET 0000 C C THIS SUBROUTINE SOLVES A MAX-FLOW-MIN-CUT PROBLEM USING C DINIC'S ALGORITHM. THE CODE IS TAKEN FROM "COMBINATORIAL C ALGORITHMS", ACADEMIC PRESS, WRITTEN BY A. NIJENHUIS C AND H.S. WILF. THERE ARE THREE MINOR CHANGES: (1) STATEMENT C LABELS ARE RENUMBERED. (2) SOME DATA DECLARATION STATEMENTS C AND THE FORMAL PARAMETER LIST HAVE BEEN MODIFIED. (3) THE C WAY OF SUBSCRIPT CONSTRUCTION FOR SOME OF THE ARRAYS IS C MODIFIED. THE MODIFICATIONS ARE MAINLY FOR COMPLIANCE WITH C ANSI FORTRAN STANDARD. C THANKS ARE DUE TO THE AUTHORS AND PUBLISHER OF C 'COMBINATORIAL ALGORITHMS' FOR THEIR PERMISSION TO INCLUDE C THIS SUBROUTINE. C INTEGER C,E,P,Q,RD,WR,DELTA,SINK,SOURCE,FLOVAL INTEGER ENDPT(4,1),CUT(1) INTEGER CAP(32,32),VERT(32,32),AUX(32) C C ENDPT AND CUT ARE EXPLAINED IN THE SUBROUTINE 'LOCATE'. C CAP, VERT AND AUX ARE WORKING STORAGE, WHOSE LENGTH IS C EQUAL TO THE NUMBER OF VARIABLE POINTS PLUS 2. C C INITIALIZATION. DO 2 I=1,N DO 1 J=1,N CAP(I,J)=0 1 CONTINUE 2 CONTINUE DO 3 I=1,E I1=ENDPT(1,I) I2=ENDPT(2,I) CAP(I1,I2)=ENDPT(3,I) 3 CONTINUE DO 5 I=1,N K=0 DO 4 J=1,N IF(CAP(I,J)+CAP(J,I).EQ.0) GO TO 4 K=K+1 VERT(I,K)=J 4 CONTINUE VERT(I,N)=K 5 CONTINUE NMIN=-N-1 FLOVAL=0 C C SCANNING AND LABELING 6 LBLSNK=N DO 7 I=1,N CUT(I)=NMIN 7 CONTINUE RD=0 WR=0 P=SOURCE LABEL=-1 8 M=VERT(P,N) I=1 9 IF(I.GT.M) GO TO 13 Q=VERT(P,I) IF(CAP(P,Q).EQ.0) GO TO 12 IF(Q.EQ.SINK) LBLSNK=-LABEL IF(CUT(Q)-LABEL) 10,11,12 10 CUT(Q)=LABEL WR=WR+1 AUX(WR)=Q 11 I=I+1 GO TO 9 12 VERT(P,I)=VERT(P,M) VERT(P,M)=Q M=M-1 GO TO 9 13 CUT(P)=M RD=RD+1 IF(RD.GT.WR) GO TO 24 P=AUX(RD) IF(CUT(P)+LBLSNK.EQ.0) GO TO 14 LABEL=CUT(P)-1 GO TO 8 C C CONSTRUCTION OF PATH FROM SOURCE TO SINK 14 Q=SOURCE K=0 15 K=K+1 AUX(K)=Q IF(K.GT.LBLSNK) GO TO 19 16 P=AUX(K) 17 M=CUT(P) IF(M.EQ.0) GO TO 18 Q=VERT(P,M) GO TO 15 18 K=K-1 IF(K.EQ.0) GO TO 6 P=AUX(K) CUT(P)=CUT(P)-1 GO TO 17 19 IF(Q.NE.SINK) GO TO 18 DELTA=CAP(P,Q) DO 20 I=2,K I1=AUX(I-1) I2=AUX(I) DELTA=MIN0(DELTA,CAP(I1,I2)) 20 CONTINUE 21 K=K-1 IF(K.EQ.0) GO TO 23 P=AUX(K) C=CAP(P,Q)-DELTA IF(C.GT.0) GO TO 22 CUT(P)=CUT(P)-1 KO=K 22 CAP(P,Q)=C CAP(Q,P)=CAP(Q,P)+DELTA Q=P GO TO 21 23 FLOVAL=FLOVAL+DELTA K=KO GO TO 16 C C EXIT PROCEDURE. 24 DO 25 I=1,N CUT(I)=MIN0(1,CUT(I)-NMIN) 25 CONTINUE DO 26 I=1,E I1=ENDPT(1,I) I2=ENDPT(2,I) ENDPT(4,I)=ENDPT(3,I)-CAP(I1,I2) 26 CONTINUE RETURN END 18 3 4 0 3 2 3 0 1 2 1 0 3 2 3 1 1 2 1 2 9 1 2 2 3 4 0 1 3 1 0 3 3 3 0 9 1 1 2 2 1 3 2 2 2 4 1 5 20 0 21 14 9 7 21 0 34 24 32 14 34 0 14 36 9 24 14 0 8 7 32 36 8 0 50 49 81 46 52 80 83 48 8 33 99 0 50 76 38 40 70 32 30 92 71 63 77 31 62 5 2 85 13 37 19 64 17 59 49 75 52 44 88 94 73 32 27 72 2 7 66 79 1 19 22 76 50 68 56 87 83 69 58 36 97 24 64 49 52 1 74 8 88 84 53 84 46 74 92 45 29 19 54 71 26 51 46 49 93 34 46 35 19 28 21 15 24 31 41 89 22 92 97 99 5 20 0 21 14 9 7 21 0 34 24 32 14 34 0 14 36 9 24 14 0 8 7 32 36 8 0 33 0 50 48 46 38 32 92 80 99 30 8 40 70 52 50 49 83 76 81 37 64 71 85 31 49 44 94 5 19 88 13 75 52 62 17 63 2 59 77 19 76 73 79 72 56 69 36 7 22 58 1 87 83 2 50 32 66 68 27 84 84 97 8 49 92 19 71 1 53 54 88 45 29 52 46 24 74 74 64 28 15 26 35 49 41 92 99 34 21 97 19 89 22 93 24 51 46 31 46 5 3 0 2 2 2 2 2 0 20 1 0 2 20 0 0 0 2 1 0 0 40 2 0 0 40 0 10 0 0 4 1 4 4 1 4 4 5 4 4 5 4 3 5 0 1 1 1 0 1 1 1 0 1 1 6 1 6 4 1 1 1 1 1 1 1 1 1 3 5 0 1 0 1 0 1 0 1 0 3 2 2 0 0 2 2 2 4 4 4 0 2 6 4 3 5 0 1 0 1 0 1 0 1 0 2 3 0 2 0 2 2 4 2 4 2 4 6 0 4 1 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 15 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 20 1 4 2 15 9 0 45 3 7 5 0 0 1 50 4 0 12 32 4 22 7 5 15 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 15 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6 20 0 5 2 3 12 8 5 0 6 40 8 6 2 6 0 1 18 7 3 40 1 0 9 13 12 8 18 9 0 4 8 6 7 13 4 0 4 2 15 9 0 45 3 7 5 0 0 1 50 4 0 12 32 4 22 7 4 2 15 9 0 45 3 7 5 0 0 1 50 4 0 12 32 4 22 7 4 2 15 9 0 45 3 7 5 0 0 1 50 4 0 12 32 4 22 7 4 2 15 9 0 45 3 7 5 0 0 1 50 4 0 12 32 4 22 7 4 2 15 9 0 45 3 7 5 0 0 1 50 4 0 12 32 4 22 7 4 2 15 9 0 45 3 7 5 0 0 1 50 4 0 12 32 4 22 7 6 20 0 5 2 3 12 8 5 0 6 40 8 6 2 6 0 1 18 7 3 40 1 0 9 13 12 8 18 9 0 4 8 6 7 13 4 0 0 0 0 1 2 0 4 0 0 0 9 5 12 0 2 8 0 2 80 99 0 0 1 0 7 8 2 4 9 2 0 10 4 6 8 6 0100 24 73 0 2 1 2 0 3 4 5 0 1 6 9 1 0 5 2 0 4 0153 9 8 0 0 0 0 0 4 3 0 5 3 0 1 1 1 0 6 49 88 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 22 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 20 0 5 2 3 12 8 5 0 6 40 8 6 2 6 0 1 18 7 3 40 1 0 9 13 12 8 18 9 0 4 8 6 7 13 4 0 0 0 1 0 7 8 2 4 9 2 98 10 4 6 8 6 0 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 2 0 4 0 0111 9 5 12 0 2 8 0 2 0 0 0 2 1 2 0 3 4 5 0 57 6 9 1 0 5 2 0 4 0 8 9 8 0 0 0 0 0 4 3 1025 3 0 1 1 1 0 6 0 0 24 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 20 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 147 0 0 1 2 0 4 0 0 0 9 5 12 0 2 8 0 2 0 0 280 0 1 0 7 8 2 4 9 2 0 10 4 6 8 6 0 2 3 0 230 22 0 0 0 0 0 4 3 0 5 3 0 1 1 1 0 6 1 0 30 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 4 99 1 2 0 3 4 5 0 1 6 9 1 0 5 2 0 4 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 20 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 280 0 1 0 7 8 2 4 9 2 0 10 4 6 8 6 0 2 3 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 99 1 2 0 3 4 5 0 1 6 9 1 0 5 2 0 4 0 0 30 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 147 0 0 1 2 0 4 0 0 0 9 5 12 0 2 8 0 2 0 0 230 22 0 0 0 0 0 4 3 0 5 3 0 1 1 1 0 6 1 0 6 20 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 4 2 15 9 0 45 3 7 5 0 0 1 50 4 0 12 32 4 22 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 30 20 1 1 1 1 22 15 0 3 1 1 1 1 1 1 21 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 2 0 4 0 0 0 9 5 12 0 2 8 0 2 0 24 4 99 1 2 0 3 4 5 0 1 6 9 1 0 5 2 0 4 0 0 7 2 5 10 50500100.00 3 5 10 30400200.00 3 4 10 50500150.00 10 20 20 50500200.00 15 20 25 50500300.00 20 30 30 25400250.00 30 50 50 30500500.00