using System;
using System.IO;
using System.Diagnostics;

namespace NetFlow
{
	/// <summary>
	/// Summary description for MCNF
	/// </summary>
	public class MCNF 
	{
	   #region definizioni globali classe
      static int MAXDIM = 300000;
      static int LARGE  = 20000000;

      float TCOST;

      StreamReader fp;
      StreamWriter flog;
      StreamWriter fout;
      System.Random rnd = new Random(555);

      bool REPEAT,SWITCH,FEASBL,QUIT,POSIT,SINGLEONLY,stop;

      int N,IA,NSORC,NSINK,NVERI,I,J,M,NA,I1,I2,T3,ARC,SCAPIN,SCAPOU,CAPOUT,CAPIN,T1,T2,NDFCT,NUMNONZERO,INITHRESH,
         NLABEL,TP,TS,DELX,DELPRC,NB,RDCOST,INITCOUNT,DEFCIT,INDEF,NODE,NODE2,NARC,DP,DX,DXTMP,AUGNOD,
	      NAUGNOD,NSCAN,DM,IB,ROOT,DLX,NSAVE, risultato, successo;

      int[] STARTN= new int[MAXDIM], ENDN= new int[MAXDIM], C= new int[MAXDIM], U= new int[MAXDIM], 
            DFCT= new int[MAXDIM], DFCT1= new int[MAXDIM], B= new int[MAXDIM],
            CAP= new int[MAXDIM], RC= new int[MAXDIM], X= new int[MAXDIM], FIN= new int[MAXDIM], 
            FOU= new int[MAXDIM], NXTIN= new int[MAXDIM], NXTOU= new int[MAXDIM],
	         SAVE= new int[MAXDIM],LABEL= new int[MAXDIM],PRDCSR= new int[MAXDIM];


      bool[] MARK= new bool[MAXDIM], SCAN= new bool[MAXDIM];
      #endregion

      public int Start(int[,] TabOD, int nTabOD, int nGraviab, int[] SorgVert, int[] SorgDfct, 
                       int[] Coef1, int[] Coef2, int[] M, int[] FlussiSim)
      {  int tmp,tmp2,tmp3;
         int i,j,k,cont,sum;

         //lettura dati da file
         try
         {  fp = new StreamReader(@"inputBK.txt");
            flog = new StreamWriter("Mcnf.log",false);
         }
         catch (Exception e)
         {  flog.WriteLine(e.Message);
            fout.WriteLine(e.Message);
            return(0);
         }

         N = Convert.ToInt32(fp.ReadLine());
         IA= Convert.ToInt32(fp.ReadLine());

         //inizializzazione del vettore dei nodi //
         for (tmp=1;tmp<=N; tmp++)
            DFCT[tmp]=0;
                  
         //lettura archi//
         string line;
         for (tmp=1; tmp<=IA; tmp++)
         {  tmp2=Convert.ToInt32(fp.ReadLine());
	         STARTN[tmp]=tmp2;
         	
	         tmp2=Convert.ToInt32(fp.ReadLine());
	         ENDN[tmp]=tmp2;

            line = fp.ReadLine();
	         tmp2=Convert.ToInt32(line);
	         //C[tmp]=tmp2; //costo         	
	         tmp2=Convert.ToInt32(fp.ReadLine());
	         //U[tmp]=tmp2; //capacità
	         
	         if(M[tmp]<=0)
	            M[tmp]=5000;
	            
	         if(tmp<=nGraviab)
	         {  C[tmp]=Coef1[tmp-1];
	            U[tmp]=M[tmp-1];
	         }
	         else if(tmp<=2*nGraviab)
	         {  C[tmp]=Coef2[tmp-1-nGraviab];
	            U[tmp]=5000;
	         }
	         else
	         {  C[tmp]=1000;
	            U[tmp]=5000;
	         }
	         FlussiSim[tmp]=15+rnd.Next(10);
         }

         fp.Close();
         flog.WriteLine("Letto il primo file");

         // ------------------------------------------------------ vettore  sorgenti e pozzi
         fp = new StreamReader("C:/temp/inputDFCT.txt");
         fp.Close();
         flog.WriteLine("Letto file sorgenti e pozzi");
         
         NSORC = 1;
         for(j=0;j<nTabOD;j++)
         {  if((j%10) == 0)
            {  flog.WriteLine("======================================= > Iterazione "+j);
               Trace.WriteLine("Simulazione sorgente "+j+"/"+nTabOD);
            }

            cont=sum=0;
            
            for(tmp=1; tmp<=IA; tmp++)
	            if(tmp<=nGraviab)
	            {  C[tmp]=Coef1[tmp-1];
	               U[tmp]=M[tmp-1]/2;
	            }
	            else if(tmp<=2*nGraviab)
	            {  C[tmp]=Coef2[tmp-1-nGraviab];
	               U[tmp]=M[tmp-1]/2;
	            }
	            else
	            {  C[tmp]=10000;
	               U[tmp]=10000;
	            }
         
            for(i=0;i<nTabOD;i++)
            {  if(i != j)
               {  if(TabOD[i,j]>0)
                  {  cont++;
                     sum+=TabOD[i,j];
                  }
                  DFCT[i+1]=TabOD[i,j];
               }
               //flog.WriteLine(i+1);
               //flog.WriteLine(DFCT[i+1]);
            }
            DFCT[SorgVert[j]]=-sum;
            //if(SorgDfct[j] != sum)
            //   flog.WriteLine("ERRORETTO! j= {0,3} SorgDfct[j] = {1,5} sum = {2,5}",j,SorgDfct[j],sum);
         
            successo = MINFLOW(N,IA,NSORC,NSINK,STARTN,ENDN,C,U,DFCT);
            
            if(successo>0)
            {  k=1;
               for(i=1;i<=nGraviab;i++)
               {  FlussiSim[i]+=X[k];
                  k++;
                  FlussiSim[i]+=X[k];
                  k++;
                  FlussiSim[i]+=X[i+nGraviab];
                  FlussiSim[i]+=X[i+nGraviab+1];
               }
            }
            else
            {  flog.WriteLine("SIMULAZIONE: problema, j="+j);  
               DFCT[SorgVert[j]]=0;
               //flog.Close();
               //return(0);
            }
         }
         
         //flog.WriteLine("Vettore x dei flussi");//
         for (I=1; I<=NA; I++)           
         {  FlussiSim[I]=Convert.ToInt32(FlussiSim[I]*2.03);
            flog.WriteLine("{0,5}{1,5}{2,5}{3,5}{4,5}{5,5}{6,7}",
               I,STARTN[I],ENDN[I],Coef1[I-1],M[I-1],Coef2[I-1],FlussiSim[I]);
            
         }
         flog.WriteLine("Fine");
         flog.Close();
         
         return(successo);
      }  //fine start


      int MINFLOW(int N1,int IA1, int NSORC1, int NSINK1,
                  int[] STARTN1,int[] ENDN1,int[] C,int[] U1, int[] DFCT1)
      {  //fout = new StreamWriter(@"outputBK.txt",false);
               
         risultato=0;
         N=N1;
         IA=IA1;
         for ( I=1;I<=IA; I++)
         {  NSORC=NSORC1;
            NSINK=NSINK1;
            STARTN[I]=STARTN1[I];
            ENDN[I]=ENDN1[I];
            U[I]=U1[I];
         }

         for (I=1;I<=N;I++)  DFCT[I]=DFCT1[I];
      
         for (I=1;I<=N;I++)  B[I]=0;

         M=0;

         for  (I=1;I<=IA;I++)
         {  if (STARTN[I]==N+1)
               B[ENDN[I]]=-U[I];
            else 
               if (ENDN[I]==N+2) 
                  B[STARTN[I]]=U[I];
               else
               {  M=M+1;
                  if (U[I]>LARGE) U[I]=LARGE;
                  if (C[I]>LARGE) C[I]=LARGE;
                  if (C[I]<-LARGE) C[I]=-LARGE;
                  C[M]=C[I];
                  U[M]=U[I];
                  STARTN[M]=STARTN[I];
                  ENDN[M]=ENDN[I];
               }
         }//fine for //

         NA=M;
         REPEAT=false;
         stop=false;

         for (I=1;I<=NA;I++)
            CAP[I]=U[I];

         INIDAT();

         // Set initial dual prices to zero //
         for (I=1;I<=NA;I++)
            RC[I]=C[I];
               
         // CPU_TIME(t1)//
         RELAX();

         //   CPU_TIME(t2)//

         if (!stop)
         {  risultato=1;
         
            //flog.WriteLine("Vettore x dei flussi");//
            //for (I=1; I<=NA; I++)           
            //{  fout.WriteLine("{0,5}{1,5}{2,5}{3,7}",I,STARTN[I],ENDN[I],X[I]);
               //flog.WriteLine(X[I]);
            //}

            TCOST=0;

            for (I=1; I<=NA; I++) 
               TCOST=TCOST + X[I]*C[I];
             
            flog.WriteLine("Costo ottimale totale pari a "+TCOST);//
            //fout.WriteLine(TCOST);
         }

         //fout.Close();
         return risultato ;
      }
      //--------------------------------------------------------------------------------------------------------------------------//

      void  INIDAT()
      {  //  FOU[I]     = First arc leaving node I.
         //  NXTOU[J]   = Next arc leaving the head node of arc J.
         //  FIN[I]     = First arc entering node I.
         //  NXTIN[J]   = Next arc entering the tail node of arc J.//

         int[]  TEMPIN= new int[MAXDIM],  TEMPOU= new int[MAXDIM];

         // construct data structure required by RELAX //
         for (I=1; I<=N; I++) //25//
         {  FIN[I]=0;
            FOU[I]=0;
            TEMPIN[I]=0;
            TEMPOU[I]=0;
         }

         for  (I=1;I<=NA;I++)
		   {  NXTIN[I]=0;
            NXTOU[I]=0;
            I1=STARTN[I];
            I2=ENDN[I];
            if (FOU[I1]!=0) 
              NXTOU[TEMPOU[I1]]=I;
            else
              FOU[I1]=I;
            TEMPOU[I1]=I;
            if (FIN[I2]!=0) 
               NXTIN[TEMPIN[I2]]=I;
            else
               FIN[I2]=I;
            TEMPIN[I2]=I;
		   }
         return; // fine inidat//
      }

      //--------------------------------------------------------------------//
      void RELAX()
      {  /* Reduce arc capacity as much as possible w/out changing the problem 
            If this is a sensitivity run via routine SENSTV skip the 
            initialization by setting REPEAT to true in the calling program

            The initialization (from here up to line 70) 
            can be skipped (by setting REPEAT to true) if the calling program
            places in common user-chosen values for the arc flows, residual arc 
            capacities, nodal deficits and reduced costs. It is mandatory that arc 
            flows and residual costs satisfy complementary slackess, on each arc, 
            and that the DFCT  array properly correspond to the initial arc flows
         */
         if (REPEAT) goto settantacinque;
          
         for ( NODE=1;NODE<=N; NODE++) //40//
         {  SCAPOU=0;
            ARC=FOU[NODE];
            if(NODE==204)
               ARC=FOU[NODE];
quarantuno:
            if (ARC>0)
            {  SCAPOU=(LARGE < (SCAPOU+U[ARC])  ? LARGE : (SCAPOU+U[ARC])  );
               ARC=NXTOU[ARC];
               goto quarantuno;
   		   }
            CAPOUT=(LARGE < (SCAPOU+DFCT[NODE]) ? LARGE : (SCAPOU+DFCT[NODE] ) ) ;
         		
	         if (CAPOUT<0) 
            {  // PROBLEM IS INFEASIBLE - EXIT//
               fout.WriteLine("EXIT DURING INITIALIZATION");
               fout.WriteLine("EXOGENOUS FLOW INTO NODE "+NODE+" EXCEEDS OUT CAPACITY");
               flog.WriteLine("EXIT DURING INITIALIZATION");
               flog.WriteLine("EXOGENOUS FLOW INTO NODE "+NODE+" EXCEEDS OUT CAPACITY");
               PRINTFLOWS(NODE);
               goto quattrocento;
            }

            SCAPIN=0;
            ARC=FIN[NODE];
quarantatre:
            if (ARC>0) 
		      {  //if(CAPOUT<U[ARC])
		         //   flog.WriteLine("Node "+NODE+" decr. arc "+ARC+" to "+CAPOUT);
		         U[ARC]=(U[ARC]<CAPOUT ? U[ARC] : CAPOUT);
               SCAPIN=(LARGE<(SCAPIN+U[ARC]) ? LARGE:(SCAPIN+U[ARC] )) ;
               ARC=NXTIN[ARC];
               goto quarantatre;
            }

            CAPIN=(LARGE<(SCAPIN-DFCT[NODE]) ? LARGE:(SCAPIN-DFCT[NODE]));
                 
	         if (CAPIN<0)
            {  // PROBLEM IS INFEASIBLE - EXIT//
               fout.WriteLine("EXIT DURING INITIALIZATION");
               fout.WriteLine("EXOGENOUS FLOW OUT OF NODE "+NODE+" EXCEEDS OUT CAPACITY");
               flog.WriteLine("EXIT DURING INITIALIZATION");
               flog.WriteLine("EXOGENOUS FLOW OUT OF NODE "+NODE+" EXCEEDS OUT CAPACITY");
               PRINTFLOWS(NODE);
               goto quattrocento;
            }

            ARC=FOU[NODE];
quarantacinque:
            if (ARC>0) 
            {  U[ARC]=(U[ARC]<CAPIN ? U[ARC]:CAPIN);
               ARC=NXTOU[ARC];
               goto quarantacinque;
		      }
         }// fine for 40//


         // initialize the arc flows and the nodal deficits //
         // note that U[ARC] is redefined as the residual capacity of ARC //

         for ( ARC=1; ARC<=NA; ARC++) //70//
         {  if (RC[ARC]<0)
            {  X[ARC]=U[ARC];
               U[ARC]=0;
               T1=STARTN[ARC];
               DFCT[T1]=DFCT[T1]+X[ARC];
               T1=ENDN[ARC];
               DFCT[T1]=DFCT[T1]-X[ARC];
            }
            else
		      {  X[ARC]=0;}
         } // fine 70//

         // INITIALIZE OTHER VARIABLES //
settantacinque:
            FEASBL=true;
            NDFCT=N;
            NUMNONZERO=0;
            SWITCH=false;

         // RELAX DOES TWO KIND OF ITERATIONS, SINGLE-NODE AND MULTI-NODE.
         // THE FIRST ARE CHEAP SINCE THEY INVOLVE JUST A SINGLE NODE;
         // THE SECOND ARE MORE EXPENSIVE. IT WAS FOUND MORE EFFICIENT
         // TO ALLOW SINGLE-NODE ITERATIONS ONLY IN THE INITIAL PHASE OF THE
         // ALGORITHM. THE PARAMETER INITHRESH GIVES THE NUMBER OF CYCLES FOR
         // WHICH MULTI-NODE ITERATIONS ARE SKIPPED. //

         if (REPEAT) 
		      INITHRESH=1;
         else
		      INITHRESH=2;
         
         SINGLEONLY=true;

	         // INITIALIZE COUNTER OF NUMBER OF CYCLES PERFORMED //

               INITCOUNT=0;

               for ( I=1;I<=N;I++)//76//
               {
                     MARK[I]=false;
                     SCAN[I]=false;
               }
               NLABEL=0;

	         // set threshold for switch //
	         //  RELAX USES AN ADAPTIVE STRATEGY FOR DECIDING WHETHER TO
            // continue THE SCANNING PROCESS UNTIL ALL LABELED NODES
            // HAVE BEEN SCANNED. THETHRESHOLD 
            // PARAMETERS TP, AND TS THAT CONTROL
            // THIS STRATEGY ARE SET IN THE NEXT TWO LINES.//

               TP=10;
               TS=N/15;

         // start relaxation algorithm //
         // loop repeatedly over all nodes in sequence until termination //

         //cntzm = 0;//

ottanta:
         for( NODE=1;NODE<=N;NODE++) // for 100 grande//
         {
            DEFCIT=DFCT[NODE];
	         if (DEFCIT==0) 
		         goto cento;
            else
		         { 
		            NUMNONZERO=NUMNONZERO+1;
                    
                  if (DEFCIT>0)
			            POSIT=true;
		            else			    
			            POSIT=false;
         		  
               }

         // ATTEMPT A SINGLE NODE ITERATION FROM NODE //

         if (POSIT)
         {
	         // CASE OF NODE W/ POSITIVE DEFICIT //
               DELX=0;
               DELPRC=LARGE;
               NB=0;
	         // check outgoing arcs from NODE //

            ARC=FOU[NODE];
cinquecento:
	         if (ARC>0) 
            {
               RDCOST=RC[ARC];
               if (RDCOST>0) goto centoquarantacinque;
               if (RDCOST==0) 
                  {
                  if (X[ARC]>0)
                  {
                        NB=NB+1;
                        SAVE[NB]=ARC;
                        DELX=DELX+X[ARC];
                     }
                  }
                  else
		         {  if (-RDCOST<DELPRC) DELPRC=-RDCOST;}
             
centoquarantacinque:
               ARC=NXTOU[ARC];
               goto cinquecento;
            }

	         // check incoming arcs to NODE //

               ARC=FIN[NODE];
cinquecentodieci:
         							
               if (ARC>0) 
               {
               RDCOST=RC[ARC];
               if (RDCOST<0) goto centoquarantasette;
               if (RDCOST==0)
               {
                  if (U[ARC]>0)
                        {
                              NB=NB+1;
                              SAVE[NB]=-ARC;
                              DELX=DELX+U[ARC];
                           }
                  }
               else
			         {if (RDCOST<DELPRC) DELPRC=RDCOST;}
centoquarantasette:
               ARC=NXTIN[ARC];
               goto cinquecentodieci;
               }

		         // TEST FOR ASCENT - if NOT POSSIBLE EXIT //

               if (DELX>DEFCIT)
               {
                  if (SINGLEONLY)
                        goto cento;
                  else
                        {
                           QUIT=false;
                           goto sedici;
                        }
               }
               else
               {
                     INDEF=DEFCIT;
                     QUIT=false;
               }
	         //end of initial node scan //

diciotto:

	         if (DELX>DEFCIT)
	         {
	         // if NO FURTHER PRICE CHANGE IS POSSIBLE EXIT //
	         // AND if SINGLE NODE ITERATIONS ONLY ARE ALLOWED TAKE ANOTHER NODE //
          
               if (SINGLEONLY) 
               {
                  DFCT[NODE]=DEFCIT;
                  goto cento;
		         }
               else
                  {
                  if (DEFCIT<INDEF) QUIT=true;
                  goto sedici;
                  }
	         }

	         // check if the problem is infeasible //

            if ((DELX<DEFCIT)&&(DELPRC==LARGE))
               {
               // The dual cost can be improved without bound  //
                 
               fout.WriteLine("DUAL COST CAN BE IMPROVED W/OUT BOUND");
               flog.WriteLine("DUAL COST CAN BE IMPROVED W/OUT BOUND");
               goto quattrocento;
	         }

	         // SKIP FLOW ADJUSTEMT if THERE IS NO FLOW TO MODifY //

            if (DELX==0) goto quattordici;

	         // Adjust the flow on balanced arcs incident of NODE to
            // maintain complementary slackness after the price change //

	         for ( J=1;J<=NB; J++)//13//
	         {
               ARC=SAVE[J];
               if (ARC>0) 
               {
                  NODE2=ENDN[ARC];
                  T1=X[ARC];
                  DFCT[NODE2]=DFCT[NODE2]+T1;
                  U[ARC]=U[ARC]+T1;
                  X[ARC]=0;
               }
               else
               {
                  NARC=-ARC;
                  NODE2=STARTN[NARC];
                  T1=U[NARC];
                  DFCT[NODE2]=DFCT[NODE2]+T1;
                  X[NARC]=X[NARC]+T1;
                  U[NARC]=0;
               }
	         }//13//

            DEFCIT=DEFCIT-DELX;
            quattordici:
            if (DELPRC==LARGE)
            {
               QUIT=true;
               goto diciannove;
               }

	         // NODE corresponds to a dual ascent direction.  Decrease
            // the price of NODE by DELPRC and compute the stepsize to the
            // next breakpoint in the dual cost //

               NB=0;
               DP=DELPRC;
               DELPRC=LARGE;
               DELX=0;
               ARC=FOU[NODE];

cinquecentoventi:
	         if (ARC>0) 
               {
               RDCOST=RC[ARC]+DP;
               RC[ARC]=RDCOST;
               if (RDCOST>0) goto quarantasette;
               if (RDCOST==0)
                  {
                        NB=NB+1;
                        SAVE[NB]=ARC;
                        DELX=DELX+X[ARC];
                     }
               else
			         { if (-RDCOST<DELPRC) DELPRC=-RDCOST;}
quarantasette:
               ARC=NXTOU[ARC];
               goto cinquecentoventi;
	            }


               ARC=FIN[NODE];
cinquecentotrenta:
         	
               if (ARC>0)
               {
               RDCOST=RC[ARC]-DP;
               RC[ARC]=RDCOST;
               if (RDCOST<0) goto quarantotto;
               if (RDCOST==0) 
                  {
                  NB=NB+1;
                  SAVE[NB]=-ARC;
                  DELX=DELX+U[ARC];
                  }
               else
		         {if (RDCOST<DELPRC) DELPRC=RDCOST;}
                 
quarantotto:
               ARC=NXTIN[ARC];
               goto cinquecentotrenta;
               }

	         // return to check if another price change is possible //

	         goto diciotto;

	         // try to perform flow augmentation at NODE //
sedici:
	         for( J=1;J<=NB; J++)  //11//
	         {
               ARC=SAVE[J];
               if (ARC>0) 
               {
                  // ARC is an outgoing arc from NODE //
                  NODE2=ENDN[ARC];
                  T1=DFCT[NODE2];
                  if (T1<0) 
                  {
                        // Decrease the total deficit by decreasing flow of ARC  //
                     QUIT=true;
                     T2=X[ARC];
                     DXTMP=(DEFCIT<(-T1) ? DEFCIT: (-T1));
                     DX=(DXTMP<T2 ? DXTMP : T2 );
                     DEFCIT=DEFCIT-DX;
                     DFCT[NODE2]=T1+DX;
                     X[ARC]=T2-DX;
                     U[ARC]=U[ARC]+DX;
                     if (DEFCIT==0) goto diciannove;
                  }
		         }
               else
                  {
                  // -ARC is an incoming arc to NODE //
                  NARC=-ARC;
                  NODE2=STARTN[NARC];
                  T1=DFCT[NODE2];
                  if (T1<0) 
                     {
                  // Decrease the total deficit by increasing flow of -ARC  //
                     QUIT=true;
                     T2=U[NARC];
                     DXTMP=(DEFCIT<(-T1) ? DEFCIT: (-T1));
                     DX=(DXTMP<T2 ? DXTMP : T2 );
                     DEFCIT=DEFCIT-DX;
                     DFCT[NODE2]=T1+DX;
                     X[NARC]=X[NARC]+DX;
                     U[NARC]=T2-DX;
                     if (DEFCIT==0) goto diciannove;
                  }
               }
	         }// fine for 11//
              
diciannove:
	         DFCT[NODE]=DEFCIT;

         // end of single node iteration for a positive deficit node //
         }
         else
         {	// CASE OF NODE WITH NEGATIVE DEFICIT //
	         DEFCIT=-DEFCIT;
            DELX=0;
            DELPRC=LARGE;
            NB=0;
            ARC=FIN[NODE];
cinquecentoquaranta:
            if (ARC>0) 
            {
               RDCOST=RC[ARC];
               if (RDCOST>0) {goto centocinquantacinque;}
               if (RDCOST==0)
               {
                  if (X[ARC]>0) 
                  {
                     NB=NB+1;
                     SAVE[NB]=ARC;
                     DELX=DELX+X[ARC];
			         }
		         }
               else
		         { if (-RDCOST<DELPRC) DELPRC=-RDCOST;}
                
centocinquantacinque:
               ARC=NXTIN[ARC];
               goto cinquecentoquaranta;
            }

            ARC=FOU[NODE];
cinquecentocinquanta:
               if (ARC>0) 
               {
               RDCOST=RC[ARC];
               if (RDCOST<0) goto centocinquantasette;
               if (RDCOST==0) 
               {
                     if (U[ARC]>0)
                        {
                        NB=NB+1;
                        SAVE[NB]=-ARC;
                        DELX=DELX+U[ARC];
                        }
               }
               else
		         {if (RDCOST<DELPRC) DELPRC=RDCOST ;}
centocinquantasette:
               ARC=NXTOU[ARC];
               goto cinquecentocinquanta;
               }

	         // TEST FOR ASCENT - if NOT POSSIBLE EXIT //

               if (DELX>DEFCIT)
               {
                  if (SINGLEONLY)
			         { goto cento;}
                  else
                  {
                        QUIT=false;
                        goto ventisei;
                  }
               }
               else
               {
                     INDEF=DEFCIT;
                     QUIT=false;
               }
              

	         // MAKE PRICE CHANGE //
ventotto:
	         // degenerate dual ascent is allowed if either SINGLEONLY = true
            // or QUIT = false//

	         if (DELX>=DEFCIT) 
	         {
               if (SINGLEONLY) 
		         {
                     if (DELX>DEFCIT) 
                     {
			            DFCT[NODE]=-DEFCIT;
	                  goto cento;
                     }
               }
               else
                  {
                     if (DEFCIT<INDEF) QUIT=true;
                     goto ventisei;
                  }
            }

	         // check if problem is infeasible //

               if ((DELX<DEFCIT)&&(DELPRC==LARGE)) 
               {        
               fout.WriteLine("DUAL COST CAN BE IMPROVED W/OUT BOUND");
               flog.WriteLine("DUAL COST CAN BE IMPROVED W/OUT BOUND");
               goto quattrocento;
               }
               if (DELX==0) goto ventiquattro;


	         // flow augmentation is possible //
               for( J=1;J<=NB; J++) //23//
               {
               ARC=SAVE[J];
               if (ARC>0) 
               {
                  NODE2=STARTN[ARC];
                  T1=X[ARC];
                  DFCT[NODE2]=DFCT[NODE2]-T1;
                  U[ARC]=U[ARC]+T1;
                  X[ARC]=0;
                  }
               else
                  {
                  NARC=-ARC;
                  NODE2=ENDN[NARC];
                  T1=U[NARC];
                  DFCT[NODE2]=DFCT[NODE2]-T1;
                  X[NARC]=X[NARC]+T1;
                  U[NARC]=0;
               }
	         }//23//

            DEFCIT=DEFCIT-DELX;
ventiquattro:
            if (DELPRC==LARGE) 
               {
                  QUIT=true;
                  goto ventinove;
               }

	         // price increase at NODE is possible //
            NB=0;
            DP=DELPRC;
            DELPRC=LARGE;
            DELX=0;
            ARC=FIN[NODE];
cinquecentosessanta:
         	  
            if (ARC>0)
	         {
               RDCOST=RC[ARC]+DP;
               RC[ARC]=RDCOST;
               if (RDCOST>0) goto cinquanta;
               if (RDCOST==0) 
               {
                  NB=NB+1;
                  SAVE[NB]=ARC;
                  DELX=DELX+X[ARC];
                  }
               else
		         { if (-RDCOST<DELPRC) DELPRC=-RDCOST;}
                 
cinquanta:
               ARC=NXTIN[ARC];
               goto cinquecentosessanta;
            }

               ARC=FOU[NODE];

cinquecentosettanta:

               if (ARC>0)
         		  
               {
               RDCOST=RC[ARC]-DP;
               RC[ARC]=RDCOST;
               if (RDCOST<0) goto cinquantacinque;
               if (RDCOST==0) 
               {
                  NB=NB+1;
                  SAVE[NB]=-ARC;
                  DELX=DELX+U[ARC];
                  }
               else
			         {if (RDCOST<DELPRC) DELPRC=RDCOST;}
                 
cinquantacinque:
               ARC=NXTOU[ARC];
               goto cinquecentosettanta;
               }

               goto ventotto;

	         // try to perform flow augmentation at NODE //
          
ventisei:
            for ( J=1;J<=NB; J++) //21//
            {
               ARC=SAVE[J];
               if (ARC>0) 
               {
                  // ARC is an incoming arc to NODE //
                  NODE2=STARTN[ARC];
                  T1=DFCT[NODE2];
                  if (T1>0)
                  {
                     QUIT=true;
                     T2=X[ARC];
                     DXTMP=(DEFCIT<T1 ? DEFCIT: T1);
                     DX=(DXTMP<T2 ? DXTMP : T2 );
                     DEFCIT=DEFCIT-DX;
                     DFCT[NODE2]=T1-DX;
                     X[ARC]=T2-DX;
                     U[ARC]=U[ARC]+DX;
                     if (DEFCIT==0) goto ventinove;
		         }
		         }
               else
                  {
                     // -ARC is an outgoing arc from NODE //
                  NARC=-ARC;
                  NODE2=ENDN[NARC];
                  T1=DFCT[NODE2];
                  if (T1>0) 
                  {
                     QUIT=true;
                     T2=U[NARC];
                     DXTMP=(DEFCIT<T1 ? DEFCIT: T1);
                     DX=(DXTMP<T2 ? DXTMP : T2 );
                     DEFCIT=DEFCIT-DX;
                     DFCT[NODE2]=T1-DX;
                     X[NARC]=X[NARC]+DX;
                     U[NARC]=T2-DX;
                     if (DEFCIT==0) goto ventinove;
                  }
               }//fine else//
	         }//21//

ventinove:
	         DFCT[NODE]=-DEFCIT;

            // end of single node iteration for a negative deficit node //
         }


         // if single node iteration has succeeded go for another node //

         if (QUIT) goto cento;

         // do a multi-node operation from NODE //

         if (NDFCT<TP) 
            SWITCH=true;
         else
            SWITCH=false;
                

         // UNMARK NODES LABELED EARLIER //

         for ( J=1; J<=NLABEL; J++)//90//
	         {
                     NODE2=LABEL[J];
                     MARK[NODE2]=false;
                     SCAN[NODE2]=false;
            }// 90//

         // INITIALIZE LABELING //

                  NAUGNOD=0;
                  NLABEL=1;
                  LABEL[1]=NODE;
                  MARK[NODE]=true;
                  PRDCSR[NODE]=0;

         // SCAN STARTING NODE //

                  SCAN[NODE]=true;
                  NSCAN=1;
                  DM=DFCT[NODE];
                  DELX=0;
                  for ( J=1;J<=NB; J++) //95//
                  {
                     ARC=SAVE[J];
                     if (ARC>0) 
                     {
                     if (POSIT) 
				         {NODE2=ENDN[ARC];}
                     else
				         { NODE2=STARTN[ARC];}
                     
                     if (!MARK[NODE2]) 
                        {
				         NLABEL=NLABEL+1;
				         LABEL[NLABEL]=NODE2;
				         PRDCSR[NODE2]=ARC;
				         MARK[NODE2]=true;
				         DELX=DELX+X[ARC];
                        }
                     }
                  else
                     {
				         NARC=-ARC;
				         if (POSIT) 
					         { NODE2=STARTN[NARC];}
				         else
					         { NODE2=ENDN[NARC];}

				         if (!MARK[NODE2])
				         {
				         NLABEL=NLABEL+1;
				         LABEL[NLABEL]=NODE2;
				         PRDCSR[NODE2]=ARC;
				         MARK[NODE2]=true;
				         DELX=DELX+U[NARC];
				         }
                  }
		         }//95//

         // start scanning labeled nodes //

centoventi:
            NSCAN=NSCAN+1;
            
         // check to see if SWITCH needs to be set //

            if (!SWITCH) 
		         if ((NSCAN>TS)&&(NDFCT<TS)){ SWITCH=true;}
            

         // scan next node on the list of labeled nodes 
         // scanning will continue until either an overestimate of the residual 
         // capacity across the cut corresponding to the scanned set of nodes (called
         // DELX) becomes less than the absolute value of the total deficit of 
         // the scanned nodes (called DM), or else an augmenting path is found. //

            I=LABEL[NSCAN];
            SCAN[I]=true;
            if (POSIT) 
            {
                           
               // scanning node I for case of positive deficit //

               ARC=FOU[I];
 cinquecentottanta:
	         if (ARC>0) 
               {
                       
               // ARC is an outgoing arc from NODE //

                  if ((RC[ARC]!=0)||(X[ARC]==0)) goto centotre;
                  NODE2=ENDN[ARC];
                  if (MARK[NODE2]) goto centotre;

                  // NODE2 is not in the labeled set.  Add NODE2 to the  labeled set. //

                  PRDCSR[NODE2]=ARC;
                  if (DFCT[NODE2]<0) 
                  {
                     NAUGNOD=NAUGNOD+1;
                     SAVE[NAUGNOD]=NODE2;
                  }
                  NLABEL=NLABEL+1;
                  LABEL[NLABEL]=NODE2;
                  MARK[NODE2]=true;
                  DELX=DELX+X[ARC];
                  centotre:
                  ARC=NXTOU[ARC];
                  goto cinquecentottanta;
               }

		         ARC=FIN[I];
            
cinquecentonovanta:
         		
		         if (ARC>0)
		         {

               // ARC is an incoming arc into NODE //

                  if ((RC[ARC]!=0)||(U[ARC]==0)) goto centosei;
                  NODE2=STARTN[ARC];
                  if (MARK[NODE2]) goto centosei;

                  // NODE2 is not in the labeled set.  Add NODE2 to the  labeled set. //

                  PRDCSR[NODE2]=-ARC;
                  if (DFCT[NODE2]<0) 
                  {
                     NAUGNOD=NAUGNOD+1;
                     SAVE[NAUGNOD]=NODE2;
                  }
                  NLABEL=NLABEL+1;
                  LABEL[NLABEL]=NODE2;
                  MARK[NODE2]=true;
                  DELX=DELX+U[ARC];
                  centosei:
                  ARC=NXTIN[ARC];
                  goto cinquecentonovanta;
            }

            // correct the residual capacity of the scaned nodes cut //

               ARC=PRDCSR[I];
               if (ARC>0) 
			         {DELX=DELX-X[ARC];}
               else
			         {DELX=DELX-U[-ARC];}
              
                  // end of scanning of I for positive deficit case //
         }
         else
         {  // scanning node I for case of negative deficit //
               ARC=FIN[I];
seicento:
               if (ARC>0) 
               {
                  if ((RC[ARC]!=0)||(X[ARC]==0)) goto duecentotre;
         		
                  NODE2=STARTN[ARC];
                  if (MARK[NODE2]) goto duecentotre;
         		  
                  PRDCSR[NODE2]=ARC;
                  if (DFCT[NODE2]>0) 
                  {
                     NAUGNOD=NAUGNOD+1;
                     SAVE[NAUGNOD]=NODE2;
                  }
                  NLABEL=NLABEL+1;
                  LABEL[NLABEL]=NODE2;
                  MARK[NODE2]=true;
                  DELX=DELX+X[ARC];
                  duecentotre:
         		  
                  ARC=NXTIN[ARC];
                  goto seicento;
               }

               ARC=FOU[I];
seicentodieci:
               if (ARC>0)
	         { 
                  if ((RC[ARC]!=0)||(U[ARC]==0)) goto duecentosei;
                  NODE2=ENDN[ARC];
                  if (MARK[NODE2]) goto duecentosei;
                  PRDCSR[NODE2]=-ARC;
                  if (DFCT[NODE2]>0) 
                  {
                     NAUGNOD=NAUGNOD+1;
                     SAVE[NAUGNOD]=NODE2;
                  }
                  NLABEL=NLABEL+1;
                  LABEL[NLABEL]=NODE2;
                  MARK[NODE2]=true;
                  DELX=DELX+U[ARC];
                  duecentosei:
         		  
                  ARC=NXTOU[ARC];
                  goto seicentodieci;
               }
               ARC=PRDCSR[I];
               if (ARC>0) 
	         { DELX=DELX-X[ARC];}
               else
	         {DELX=DELX-U[-ARC];}
               
         }// qui ho tolto e' la fine dell'else//

         // ADD DEFICIT OF NODE SCANNED TO DM //

               DM=DM+DFCT[I];
         	   
         // check if the set of scanned nodes correspond
         // to a dual ascent direction; if yes, perform a
         // price adjustment step, otherwise continue labeling //

               if (NSCAN<NLABEL) 
               {
		            if (SWITCH) { goto duecentodieci;}
                  if ((DELX>=DM)&&(DELX>=-DM)) goto duecentodieci;
               }

         // TRY A PRICE CHANGE //

		         if (POSIT) 
 			         ASCNT1(DM,DELX,NLABEL,AUGNOD,FEASBL, SWITCH,NSCAN);
		         else
			         ASCNT2(DM,DELX,NLABEL,AUGNOD,FEASBL, SWITCH,NSCAN);
         			
               if (!FEASBL)
                  {
                     fout.WriteLine("FOLLOWING A MULTINODE PRICE CHANGE");
                     fout.WriteLine("THE DUAL COST CAN BE IMPROVED W/OUT BOUND");
                     flog.WriteLine("FOLLOWING A MULTINODE PRICE CHANGE");
                     flog.WriteLine("THE DUAL COST CAN BE IMPROVED W/OUT BOUND");
                     goto quattrocento;
                  }
                  if (!SWITCH)
		  	         goto cento;
                  if ((SWITCH)&&(AUGNOD>0))
                  {
                     NAUGNOD=1;
                     SAVE[1]=AUGNOD;
                     }

                    // CHECK if AUGMENTATION IS POSSIBLE.
                    // if NOT return TO SCAN ANOTHER NODE. //

duecentodieci: 

                  if (NAUGNOD==0) 
		         {goto centoventi;}
               // DO AUGMENTATION //
                   
                  for ( J=1;J<=NAUGNOD; J++)
                  {
                     AUGNOD=SAVE[J];
                     if (POSIT) 
                        AUGFL1(AUGNOD);
                     else
                        AUGFL2(AUGNOD);
                  }//96//

         // return TO TAKE UP ANOTHER NODE W/ NONZERO DEFICIT //

cento:
         continue;
           
         } // fine for 100 grande//

                 
         //********** TEST FOR TERMINATION **********

         NDFCT=NUMNONZERO;

         // if THE NUMBER OF ITERATIONS PERFORMED IN THE PREVIOUS CYCLE
         // IS ZERO { EXIT; else UPDATE THE INITIALIZATION COUNTER,
         // ALLOW MULTINODE ITERATIONS if THE NUMBER OF CYCLES PERFORMED
         // EXCEEDS THE INITHRESH PARAMETER, AND GO FOR ANOTHER CYCLE. 

         if (NDFCT==0) 
		       return;
         else
         {  INITCOUNT=INITCOUNT+1;
            if (INITCOUNT==INITHRESH) SINGLEONLY=false;
            NUMNONZERO=0;

            // GO FOR ANOTHER CYCLE //
            goto ottanta;
         }

         // problem is found to be infeasible //
quattrocento :
         fout.WriteLine("THE PROBLEM IS INFEASIBLE !!!");
         flog.WriteLine("THE PROBLEM IS INFEASIBLE !!!");
         stop=true;// sistemare l'uscita'//
         return;
      }

      //-----------------------------------------
      void PRINTFLOWS (int NODE1)
      {  // This subroutine prints the deficit and the flows of 
         // arcs incident to NODE. It is used for diagnostic purposes
         // in case of an infeasible problem here. It can be used also
         // for more general diagnostic purposes. //

	      NODE=NODE1;

         fout.WriteLine("DEFICIT (I.E., NET FLOW OUT) OF NODE = "+DFCT[NODE]);
         fout.WriteLine("FLOWS AND CAPACITIES OF INCIDENT ARCS OF NODE "+NODE);
         flog.WriteLine("DEFICIT (I.E., NET FLOW OUT) OF NODE = "+DFCT[NODE]);
         flog.WriteLine("FLOWS AND CAPACITIES OF INCIDENT ARCS OF NODE "+NODE);

         if (FOU[NODE]==0) 
         {  fout.WriteLine("NO OUTGOING ARCS");
            flog.WriteLine("NO OUTGOING ARCS");
         }
         else
         {  ARC=FOU[NODE];
            cinque:
            if (ARC>0) 
            {  fout.WriteLine("ARC "+ ARC +" BETWEEN NODES "+NODE+"-"+ENDN[ARC]);
               fout.WriteLine("FLOW = "+X[ARC]);
               fout.WriteLine("RESIDUAL CAPACITY = "+U[ARC]);
               flog.WriteLine("ARC "+ ARC +" BETWEEN NODES "+NODE+"-"+ENDN[ARC]);
               flog.WriteLine("FLOW = "+X[ARC]);
               flog.WriteLine("RESIDUAL CAPACITY = "+U[ARC]);
               ARC=NXTOU[ARC];
               goto cinque;
            }
         }

         if (FIN[NODE]==0) 
         {  fout.WriteLine("NO INCOMING ARCS\n");
            flog.WriteLine("NO INCOMING ARCS\n");
         }
         else
         {  ARC=FIN[NODE];
            dieci:
            if (ARC>0)
            {  fout.WriteLine("ARC "+ ARC +" BETWEEN NODES "+STARTN[ARC]+"-"+NODE);
               fout.WriteLine("FLOW = "+X[ARC]);
               fout.WriteLine("RESIDUAL CAPACITY = "+U[ARC]);
               flog.WriteLine("ARC "+ ARC +" BETWEEN NODES "+STARTN[ARC]+"-"+NODE);
               flog.WriteLine("FLOW = "+X[ARC]);
               flog.WriteLine("RESIDUAL CAPACITY = "+U[ARC]);
               ARC=NXTIN[ARC];
               goto dieci;
            }
         }
         return;
      }

      // -----------------------------------------------------------------------------------------
      void AUGFL1( int AUGNOD1)
      {  // This subroutine performs the flow augmentation step.
         // A flow augmenting path has been identified in the scanning
         // step and here the flow of all arcs positively (negatively)
         // oriented in the flow augmenting path is decreased (increased)
         // to decrease the total deficit. //


         // A flow augmenting path ending at AUGNOD is found.
         // Determine DX, the amount of flow change. //

	      AUGNOD=AUGNOD1;

            DX=-DFCT[AUGNOD];
            IB=AUGNOD;
            while (PRDCSR[IB]!=0)
            {
            ARC=PRDCSR[IB];
            if (ARC>0) 
               {
               DX=(DX<X[ARC] ? DX : X[ARC] );
               IB=STARTN[ARC];
               }
            else
            {
               DX=(DX<U[-ARC] ? DX:U[-ARC]);
               IB=ENDN[-ARC];
               }
            } 
            ROOT=IB;
            DX=(DX<DFCT[ROOT] ? DX:DFCT[ROOT]  );
            if (DX <= 0) return;

            // Update the flow by decreasing (increasing) the flow of
            // all arcs positively (negatively) oriented in the flow
            // augmenting path.  Adjust the deficits accordingly. //

            DFCT[AUGNOD]=DFCT[AUGNOD]+DX;
            DFCT[ROOT]=DFCT[ROOT]-DX;
            IB=AUGNOD;
            while (IB!=ROOT)
            {
            ARC=PRDCSR[IB];
            if (ARC>0) 
               {
               X[ARC]=X[ARC]-DX;
               U[ARC]=U[ARC]+DX;
               IB=STARTN[ARC];
            }
            else
               {
               NARC=-ARC;
               X[NARC]=X[NARC]+DX;
               U[NARC]=U[NARC]-DX;
               IB=ENDN[NARC];
            }
        }
        return;
     }

      // -----------------------------------------------------------------------------------------------
      void ASCNT1(int DM1,int DELX1,int NLABEL1,int AUGNOD1, bool FEASBL1, bool SWITCH1, int NSCAN1)
      {  // This subroutine essentially performs the multi-node
         // price adjustment step.  It first checks if the set
         // of scanned nodes correspond to a dual ascent direction.
         // If yes, then decrease the price of all scanned nodes.
         // There are two possibilities for price adjustment:
         // If SWITCH=true then the set of scanned nodes 
         // corresponds to an elementary direction of maximal 
         // rate of ascent, in which case the price of all scanned
         // nodes are decreased until the next breakpoint in the
         // dual cost is encountered.  At this point some arc
         // becomes balanced and more node(s) are added to the 
         // labeled set.
         // If SWITCH=false and the set of scanned nodes truly correspond
         // to an ascent direction, the prices of all scanned nodes
         // are decreased until the rate of ascent becomes
         // negative (this corresponds to the price adjustment
         // step in which both the line search and the degenerate
         // ascent iteration are implemented).  Otherwise we exit this
         // subroutine (to continue scanning).//

         // Store the arcs between the set of scanned nodes and
         // its complement in SAVE and compute DELPRC, the stepsize
         // to the next breakpoint in the dual cost in the direction
         // of decreasing prices of the scanned nodes. //


	         DM=DM1 ;
		      DELX=DELX1;
		      NLABEL=NLABEL1;
		      AUGNOD=AUGNOD1;
		      FEASBL=FEASBL1;
		      SWITCH=SWITCH1;
		      NSCAN=NSCAN1;

            DELPRC=LARGE;
            DLX=0;
            NSAVE=0;

         // calculate the array SAVE of arcs across the cut of scanned
         // nodes in a different way depending on whether NSCAN>N/2 or not.
         // This is done for efficiency. //

            if (NSCAN<=N/2) 
            {
            for ( I=1;I<=NSCAN; I++)//1//
            {
            NODE=LABEL[I];
            ARC=FOU[NODE];
            cento:
            if (ARC>0)
               {

                  // ARC is an arc pointing from the set of scanned
                  // nodes to its complement. //

                  NODE2=ENDN[ARC];
                  if (!SCAN[NODE2]) 
                  {
                  NSAVE=NSAVE+1;
                  SAVE[NSAVE]=ARC;
                  RDCOST=RC[ARC];
                  if ((RDCOST==0)&&(PRDCSR[NODE2]!=ARC)) {DLX=DLX+X[ARC];}
			      if ((RDCOST<0)&&(-RDCOST<DELPRC)) {DELPRC=-RDCOST;}
                  }
                  ARC=NXTOU[ARC];
                  goto cento;
		      }
               ARC=FIN[NODE];
               centodieci:
               if (ARC>0)
               {
               // ARC is an arc pointing to the set of scanned nodes from its complement. //
       
                  NODE2=STARTN[ARC];
                  if (!SCAN[NODE2]) 
                  {
                  NSAVE=NSAVE+1;
                  SAVE[NSAVE]=-ARC;
                  RDCOST=RC[ARC];
                  if ((RDCOST==0)&&(PRDCSR[NODE2]!=-ARC)) {DLX=DLX+U[ARC];}
                  if ((RDCOST>0)&&(RDCOST<DELPRC)) {DELPRC=RDCOST;}
                  }
                  ARC=NXTIN[ARC];
                  goto centodieci;
               }
      }//1//

      }//fine if scan<=N/2//

      else
      {
      for ( NODE=1;NODE<=N; NODE++)//2//
      {
            if (SCAN[NODE]) goto due;
            ARC=FIN[NODE];
centoventi:
            if (ARC>0)
               {
                  NODE2=STARTN[ARC];
                  if (SCAN[NODE2]) 
                  {
                  NSAVE=NSAVE+1;
                  SAVE[NSAVE]=ARC;
                  RDCOST=RC[ARC];
                  if ((RDCOST==0)&&(PRDCSR[NODE]!=ARC)) {DLX=DLX+X[ARC];}
                  if ((RDCOST<0)&&(-RDCOST<DELPRC)){ DELPRC=-RDCOST;}
                  }
                  ARC=NXTIN[ARC];
                  goto centoventi;
               }

               ARC=FOU[NODE];
centotrenta:
               if (ARC>0)
               {
                  NODE2=ENDN[ARC];
                  if (SCAN[NODE2])
                  {
                  NSAVE=NSAVE+1;
                  SAVE[NSAVE]=-ARC;
                  RDCOST=RC[ARC];
                  if ((RDCOST==0)&&(PRDCSR[NODE]!=(-ARC))) {DLX=DLX+U[ARC];}
                  if ((RDCOST>0)&&(RDCOST<DELPRC)) {DELPRC=RDCOST;}
                  }
                  ARC=NXTOU[ARC];
                  goto centotrenta;
               }
due:
         continue; 		      
	      }// 2//       //     markare tutti i for//

      }// fine else//

         // Check if the set of scanned nodes truly corresponds
         // to a dual ascent direction.  Here DELX+DLX is the exact
         // sum of the flow on arcs from the scanned set to the 
         // unscanned set plus the ( capacity - flow ) on arcs from
         // the unscanned set to the scanned set. 
         // If this is not the case, we set SWITCH to true
         // and exit the subroutine. //

            if (DELX+DLX>=DM)
            {
            SWITCH=true;
            AUGNOD=0;
            for ( I=NSCAN+1; I<=NLABEL;I++)
               {
			      NODE=LABEL[I];
			      if (DFCT[NODE]<0) {AUGNOD=NODE;}
               }
            return;
            }
            DELX=DELX+DLX;

      // check that the problem is feasible //

quattro:
         if (DELPRC==LARGE) 
         {

            // We can increase the dual cost without bound.
            // Therefore the primal problem is infeasible. //

            FEASBL=false;
            return;
            }

      // Decrease prices of the scanned nodes, add more 
      // nodes to the labeled set & check if a newly labeled node
      // has negative deficit. //

      if (SWITCH) 
         {
            AUGNOD=0;
            for ( I=1;I<=NSAVE; I++)//7//
               { 
               ARC=SAVE[I];
               if (ARC>0) 
                  {
                  RC[ARC]=RC[ARC]+DELPRC;
                  if (RC[ARC]==0) 
                  {
                     NODE2=ENDN[ARC];
                     PRDCSR[NODE2]=ARC;
                     if (DFCT[NODE2]<0) 
				      { AUGNOD=NODE2;}
                     else
                           {
                              if (!MARK[NODE2]) 
                              {
                                 MARK[NODE2]=true;
                                 NLABEL=NLABEL+1;
                                 LABEL[NLABEL]=NODE2;
                              }
                           }
			      }
		      }
               else
               {
                  ARC=-ARC;
                  RC[ARC]=RC[ARC]-DELPRC;
                  if (RC[ARC]==0) 
                  {
                     NODE2=STARTN[ARC];
                     PRDCSR[NODE2]=-ARC;
                     if (DFCT[NODE2]<0) 
                           AUGNOD=NODE2;
                     else
                           {
                              if (!MARK[NODE2]) 
                                 {
                                    MARK[NODE2]=true;
                                    NLABEL=NLABEL+1;
                                    LABEL[NLABEL]=NODE2;
                                 }
                           }
               }
		      }// end else arc>0//
		      }//7//

      return;
      } // fine switch//

      else
      {  // Decrease the prices of the scanned nodes by DELPRC.
         // Adjust arc flow to maintain complementary slackness with
         // the prices. //

            for ( I=1; I<=NSAVE; I++)//6//
            {
            ARC=SAVE[I];
            if (ARC>0) 
            {
                  T1=RC[ARC];
                  if (T1==0) 
                  {
                     T2=X[ARC];
                     T3=STARTN[ARC];
                     DFCT[T3]=DFCT[T3]-T2;
                     T3=ENDN[ARC];
                     DFCT[T3]=DFCT[T3]+T2;
                     U[ARC]=U[ARC]+T2;
                     X[ARC]=0;
                  }
                  RC[ARC]=T1+DELPRC;
                  if (RC[ARC]==0) DELX=DELX+X[ARC];
               }
            else
               {
               ARC=-ARC;
               T1=RC[ARC];
               if (T1==0) 
                  {
                  T2=U[ARC];
                  T3=STARTN[ARC];
                  DFCT[T3]=DFCT[T3]+T2;
                  T3=ENDN[ARC];
                  DFCT[T3]=DFCT[T3]-T2;
                  X[ARC]=X[ARC]+T2;
                  U[ARC]=0;
			      }
               RC[ARC]=T1-DELPRC;
               if (RC[ARC]==0) DELX=DELX+U[ARC];
		      }
            }// for 6//
      }// fine else//

      if (DELX<=DM) 
         {  // The set of scanned nodes still corresponds to a 
            // dual (possibly degenerate) ascent direction.  Compute
            // the stepsize DELPRC to the next breakpoint in the
            // dual cost. //

            DELPRC=LARGE;
            for ( I=1;I<=NSAVE; I++)//10//
            {
               ARC=SAVE[I];
               if (ARC>0) 
                  {
                  RDCOST=RC[ARC];
                  if ((RDCOST<0)&&(-RDCOST<DELPRC)){ DELPRC=-RDCOST;}
                  }
               else
                  {
                  ARC=-ARC;
                  RDCOST=RC[ARC];
                  if ((RDCOST>0)&&(RDCOST<DELPRC)) {DELPRC=RDCOST;}
                  }
            }//10//
         
		      if ((DELPRC==LARGE)&&(DELX==DM)){ return;}
            goto quattro;
         }

         return;
      }
                  

      // -----------------------------------------------------------------------------------
      void AUGFL2(int AUGNOD2)
      {  // an augmenting path is found.  determine flow change //

            AUGNOD=AUGNOD2;

            DX=DFCT[AUGNOD];
            IB=AUGNOD;
            while (PRDCSR[IB]!=0)
            {
            ARC=PRDCSR[IB];
            if (ARC>0) 
               {
               DX=(DX<X[ARC] ? DX : X[ARC]);
               IB=ENDN[ARC];
               }
            else
               {
               DX=(DX<U[-ARC] ? DX:U[-ARC]);
               IB=STARTN[-ARC];
            }
            }
            ROOT=IB;
            DX=(DX <(-DFCT[ROOT]) ? DX : (-DFCT[ROOT] ) );
            if (DX <= 0) return;

      // update the flow and deficits //

            DFCT[AUGNOD]=DFCT[AUGNOD]-DX;
            DFCT[ROOT]=DFCT[ROOT]+DX;
            IB=AUGNOD;
            while  (IB!=ROOT)
            {
            ARC=PRDCSR[IB];
            if (ARC>0) 
               {
               X[ARC]=X[ARC]-DX;
               U[ARC]=U[ARC]+DX;
               IB=ENDN[ARC];
               }
            else
               {
               NARC=-ARC;
               X[NARC]=X[NARC]+DX;
               U[NARC]=U[NARC]-DX;
               IB=STARTN[NARC];
               }
            }  
      return;
      }


      //-----------------------------------------//
      void ASCNT2(int DM2,int DELX2,int NLABEL2,int AUGNOD2,bool FEASBL2,bool SWITCH2, int NSCAN2)
      {  // augment flows across the cut & compute price rise //
	      DM=DM2 ;
	      DELX=DELX2;
	      NLABEL=NLABEL2;
	      AUGNOD=AUGNOD2;
	      FEASBL=FEASBL2;
	      SWITCH=SWITCH2;
	      NSCAN=NSCAN2;

         DELPRC=LARGE;
         DLX=0;
         NSAVE=0;
         if (NSCAN<=N/2)
         {
            for ( I=1; I<=NSCAN; I++)//1//
               {
                  NODE=LABEL[I];
                  ARC=FIN[NODE];
                  cento:
                  if (ARC>0)
                     {
                     NODE2=STARTN[ARC];
                     if (!SCAN[NODE2]) 
                     {
				         NSAVE=NSAVE+1;
				         SAVE[NSAVE]=ARC;
				         RDCOST=RC[ARC];
				         if ((RDCOST==0)&&(PRDCSR[NODE2]!=ARC)) {DLX=DLX+X[ARC];}
				         if ((RDCOST<0)&&(-RDCOST<DELPRC)) {DELPRC=-RDCOST;}
			         }
                     ARC=NXTIN[ARC];
                     goto cento;
		            }

                  ARC=FOU[NODE];
                  centodieci:
                  if (ARC>0)
                  {
                     NODE2=ENDN[ARC];
                     if (!SCAN[NODE2]) 
                     {
                     NSAVE=NSAVE+1;
                     SAVE[NSAVE]=(-ARC);
                     RDCOST=RC[ARC];
                     if ((RDCOST==0)&&(PRDCSR[NODE2]!=(-ARC))) {DLX=DLX+U[ARC];}
                     if ((RDCOST>0)&&(RDCOST<DELPRC)){ DELPRC=RDCOST;}
			         }
                     ARC=NXTOU[ARC];
                     goto centodieci;
                  }
            }//1//
         }// fine if scan//

         else
         {  
               
            for ( NODE=1;NODE<=N; NODE++)
               {
		         if (SCAN[NODE]) goto due;
                  ARC=FOU[NODE];
                  centoventi:
                  if (ARC>0) 
                     {
                     NODE2=ENDN[ARC];
                     if (SCAN[NODE2]) 
                     {
                     NSAVE=NSAVE+1;
                     SAVE[NSAVE]=ARC;
                     RDCOST=RC[ARC];
                     if ((RDCOST==0)&&(PRDCSR[NODE]!=ARC)) DLX=DLX+X[ARC];
                     if ((RDCOST<0)&&(-RDCOST<DELPRC)) DELPRC=-RDCOST;
                     }
                     ARC=NXTOU[ARC];
                     goto centoventi;
                  }

                  ARC=FIN[NODE];
                  centotrenta:
                  if (ARC>0)
                  {
                     NODE2=STARTN[ARC];
                     if (SCAN[NODE2]) 
                     {
                     NSAVE=NSAVE+1;
                     SAVE[NSAVE]=-ARC;
                     RDCOST=RC[ARC];
                     if ((RDCOST==0)&&(PRDCSR[NODE]!=-ARC)) DLX=DLX+U[ARC];
                     if ((RDCOST>0)&&(RDCOST<DELPRC)) DELPRC=RDCOST;
                     }
                     ARC=NXTIN[ARC];
                     goto centotrenta;
                  }
               due:
	         continue;
               }//2//
         }//else//

         if ((DELX+DLX)>=(-DM))
         {      
               SWITCH=true;
               AUGNOD=0;
               for ( I=NSCAN+1; I<=NLABEL; I++)
                  {
                  NODE=LABEL[I];
                  if (DFCT[NODE]>0){ AUGNOD=NODE;}
                  }
               return;
            }

            DELX=DELX+DLX;

         // check that the problem is feasible //
               quattro:
               if (DELPRC==LARGE)
               {
               FEASBL=false;
               return;
               }

         // INCREASE PRICES //

         if (SWITCH) 
         {      
               AUGNOD=0;
               for ( I=1;I<=NSAVE; I++)// 7//
                  {
                  ARC=SAVE[I];
                  if (ARC>0) 
			         {
                     RC[ARC]=RC[ARC]+DELPRC;
                     if (RC[ARC]==0) 
                     {
                        NODE2=STARTN[ARC];
                        PRDCSR[NODE2]=ARC;
                        if (DFCT[NODE2]>0) 
					         {  AUGNOD=NODE2;}
                         
                        else
                           {
                              if (!MARK[NODE2])
                                 {
                                    MARK[NODE2]=true;
                                    NLABEL=NLABEL+1;
                                    LABEL[NLABEL]=NODE2;
                                    }
                           }
			         }
		         }    
                  else
                  {
                     ARC=-ARC;
                     RC[ARC]=RC[ARC]-DELPRC;
                     if (RC[ARC]==0) 
			         {
                        NODE2=ENDN[ARC];
                        PRDCSR[NODE2]=-ARC;
                        if (DFCT[NODE2]>0) 
				         {AUGNOD=NODE2;}
                        else
                        {
                              if (!MARK[NODE2]) 
                              {
                                    MARK[NODE2]=true;
                                    NLABEL=NLABEL+1;
                                    LABEL[NLABEL]=NODE2;
                              }
                        }
                     
			         }
		         }
            }//7//
            return;
         }
             
         else     // dello switch//
         {
               for ( I=1;I<=NSAVE; I++)//6//
               {
               ARC=SAVE[I];
               if (ARC>0) 
                     {
                     T1=RC[ARC];
                     if (T1==0) 
                     {
                     T2=X[ARC];
                     T3=STARTN[ARC];
                     DFCT[T3]=DFCT[T3]-T2;
                     T3=ENDN[ARC];
                     DFCT[T3]=DFCT[T3]+T2;
                     U[ARC]=U[ARC]+T2;
                     X[ARC]=0;
                     }
                     RC[ARC]=T1+DELPRC;
                     if (RC[ARC]==0) DELX=DELX+X[ARC];
                  }
               else
               {
                     ARC=-ARC;
                     T1=RC[ARC];
                     if (T1==0) 
                     {
                     T2=U[ARC];
                     T3=STARTN[ARC];
                     DFCT[T3]=DFCT[T3]+T2;
                     T3=ENDN[ARC];
                     DFCT[T3]=DFCT[T3]-T2;
                     X[ARC]=X[ARC]+T2;
                     U[ARC]=0;
                     }
                  RC[ARC]=T1-DELPRC;
                  if (RC[ARC]==0) DELX=DELX+U[ARC];
               }
         }//6//
         }//  fine switch//


      if (DELX<=-DM)
      {
            DELPRC=LARGE;
            for( I=1;I<=NSAVE; I++)//10//
            {
               ARC=SAVE[I];
               if (ARC>0) 
                  {
                  RDCOST=RC[ARC];
                  if ((RDCOST<0)&&(-RDCOST<DELPRC)) DELPRC=-RDCOST;
               }
               else
               {
                  ARC=-ARC;
                  RDCOST=RC[ARC];
               if ((RDCOST>0)&&(RDCOST<DELPRC)) DELPRC=RDCOST;
		      }
            }//10//
            if ((DELPRC==LARGE)&&(DELX==-DM)) return;
            goto quattro;
         }
      return;
      }
	}
}