/* MAXFLOW.c */
/* all integers between 0 and 999 inclusively */
/* all labels on nodes between 1 and 99 inclusively */

#include <stdio.h>
int INPUTW2GRAPH(int*,int*,int*,int*,char*);
void SORTBA(int*,int*,int*,int*,int*,int*,int*,int*,int);
void inNODEout(int*,int*,int*,int*,int*,int*,int);
void flowNODEflow(int*,int*,int*,int*,int*,int*,int);

#define NN 1000
#define MM 100
#define INF 99
int FLOW[NN],SIGN[NN];
void INDEXAA(int*,int*,int);
void INDEXBBr(int*,int*,int);


void main(void)
{
 int K,Npairs,Nobj=0,
     A[NN],B[NN],  /* links A[K]--> B[K], in order by A[K] then B[K] */
     CAP[NN],INDEXA[MM],
     Ar[NN],Br[NN],  /* links Ar[K] --> Br[K], in order by Br[K] then Ar[K] */
     Cr[NN],Fr[NN],INDEXBr[MM];
 char
  /*   WG[]= "[-1,2,3,4,5,#4,5,2,12,  -2,3,5,#3,1,   -3,4,8,#1,13,  -4,6,#11,/"
            "-5,7,8,#6,9,  -6,8,#8,  -7,8,#7]"; */

     WG[] = "[-1,2,4,#5,6,&5,4,  -2,6,#6,&6,/"
              "-3,1,2,#4,2,&1,0,   -4,2,3,5,#2,2,3,&1,1,2,/"
              "-5,7,#5,&5,   -6,4,5,7,#4,4,4,&0,3,3]";

 for (K=0; K<NN; K++) FLOW[K]=SIGN[NN]=0;

 Npairs = INPUTW2GRAPH(A,B,CAP,FLOW,WG);
 for (K=0; K<Npairs; K++) {if (A[K]>Nobj) Nobj=A[K]; if (B[K]>Nobj) Nobj=B[K];}

 printf("%d directed links,    %d largest node label\n",Npairs,Nobj);
 for (K=0; K<Npairs; K++) printf("%3d,",K); puts("");
 for (K=0; K<Npairs; K++) printf("%3d,",A[K]); puts("");
 for (K=0; K<Npairs; K++) printf("%3d,",B[K]); puts("");
 for (K=0; K<Npairs; K++) printf("%3d,",CAP[K]); puts("");
 for (K=0; K<Npairs; K++) printf("%3d,",FLOW[K]); puts("");

 INDEXAA(A,INDEXA,Npairs);
 for (K=1; K<Nobj; K++) printf("%d(%d) ",K,INDEXA[K]); puts("\n");

 SORTBA(A,B,CAP,FLOW,Ar,Br,Cr,Fr,Npairs);

 for (K=0; K<Npairs; K++) printf("%3d,",K); puts("");
 for (K=0; K<Npairs; K++) printf("%3d,",Ar[K]); puts("");
 for (K=0; K<Npairs; K++) printf("%3d,",Br[K]); puts("");
 for (K=0; K<Npairs; K++) printf("%3d,",Cr[K]); puts("");
 for (K=0; K<Npairs; K++) printf("%3d,",Fr[K]); puts("");

 INDEXBBr(Br,INDEXBr,Npairs);
 for (K=1; K<=Nobj; K++) printf("%d(%d) ",K,INDEXBr[K]); puts("\n");

 inNODEout(A,B,INDEXA,Ar,Br,INDEXBr,Nobj);
 flowNODEflow(A,FLOW,INDEXA,Br,Fr,INDEXBr,Nobj);

 getchar();
}

   /****************************************/
   /* fast access to integers in array A */

void INDEXAA(int *A, int *INDEXA, int Npairs)
{
 int K=Npairs-1;

LP:
 while (A[K]==A[K-1]) K--;
 INDEXA[A[K]]=K;                /* printf("%d(%d) ",A[K],K); */
 if (K) {K--; goto LP;}
 return;
}

   /****************************************/
   /* fast access to integers in array Br */

void INDEXBBr(int *Br, int *INDEXBr, int Npairs)
{
 int K=Npairs-1;

LP:
 while (Br[K]==Br[K-1]) K--;
 INDEXBr[Br[K]]=K;               /*  printf("%d(%d) ",Br[K],K); getchar(); */
 if (K) {K--; goto LP;}
 return;
}

   /****************************************/
  /* sort A, B by B increasing and return it into  Ar, Br */


void SORTBA(int *A, int *B, int *C, int *F, int *Ar, int *Br, int *Cr, int *Fr, int Npairs)

{
 int I,J,K,M,     *P,*Q,         BA[NN], CF[NN];

 P=A; Q=B;
 for (K=0; K<Npairs; K++) {BA[K] = *Q*10000 + *P; P++; Q++;}
 P=C; Q=F;
 for (K=0; K<Npairs; K++) {CF[K] = *P*10000 + *Q; P++; Q++;}

 for (I=0; I<Npairs; I++)
  {
   K=I; M=BA[K];
   for (J=I+1; J<Npairs; J++) if (BA[J]<M) {K=J; M=BA[K];}
   if (K>I) {BA[K]=BA[I]; BA[I]=M;  M=CF[K]; CF[K]=CF[I]; CF[I]=M;}
  }

 P=Ar; Q=Br;
 for (K=0; K<Npairs; K++) {*P = BA[K]%10000; *Q = BA[K]/10000; P++; Q++;}
 P=Cr; Q=Fr;
 for (K=0; K<Npairs; K++) {*P = CF[K]/10000; *Q = CF[K]%10000; P++; Q++;}
 
 return;
}
  /****************************************/

void inNODEout(int *A, int *B, int *INDEXA, int *Ar, int *Br, int *INDEXBr, int Nobj)
{
 int H,I,J,K;
  puts("incoming to -> (node) -> outgoing from");

  printf("S,");

  for (K=1; K<=Nobj; K++)
  {
   J=INDEXBr[K];  H=Br[J];
   while (Br[J]==H) {printf("%d,",Ar[J]); J++;}
   printf(" (%d) ",K);
   if (K<Nobj)
    {
     I=INDEXA[K];  H=A[I];
     while (A[I]==H) {printf("%d,",B[I]); I++;}
     puts("");
    }
   else puts("D\n");
  }
 return;
}

  /****************************************/

void flowNODEflow(int *A, int *F, int *INDEXA, int *Br, int *Fr, int *INDEXBr, int Nobj)
{
 int H,I,J,K,SUMF;

 printf("x = total flow into entry node (1) ");
  printf("x = total flow out of exit node %d\n",Nobj);
 puts("total flow into each (node) = total flow out of that (node)"); 

 if (Fr[0]) printf("x+%d, (1) ",Fr[0]); else printf("%d,  (1)",Fr[0]);
 K=1;
    I=INDEXA[K];  H=A[I];   SUMF=0;
   while (A[I]==H) {SUMF+=F[I]; I++;}   printf("%d,",SUMF); puts("");


  K=2;
LP:
 J=INDEXBr[K];  H=Br[J];  SUMF=0;
 while (Br[J]==H) {SUMF+=Fr[J]; J++;}   printf("%d,",SUMF);
 printf(" (%d) ",K);
 if (K<Nobj)
  {
   I=INDEXA[K];  H=A[I];   SUMF=0;
   while (A[I]==H) {SUMF+=F[I]; I++;}   printf("%d,",SUMF); puts("");
   K++; goto LP;
  }
 puts("x\n");
 printf("x = %d\n",SUMF);
 return;
}


  /****************************************/



int MaximumFlow(int *A, int *B, int *C)
{


 return 0;
}
  /****************************************/

int INPUTW2GRAPH(int *P, int *Q, int *R1, int *R2, char *WG)
{
 int I,J,K,TCNT=0,CNT1,CNT2;

 I=0;
NEWCLUSTER:
 while (WG[I]==' ') I++;            /* pass over any blanks */
 if (WG[I]==']') {*P=0; *Q=0; *R1=0; *R2=0; return TCNT;} /* found ] = end of data */

 while (WG[I]!='-')I++;            /* start with negative integer */
  I++; K=0;
  while (WG[I]!=',') {K = 10*K + WG[I]-48; I++;}
  *P=J=K; CNT1=CNT2=0;                        /* WG[I] = , */
LP:
  I++;
  if (WG[I] == '#') goto WEIGHTS;
  K=0; while (WG[I]!=',') {K = 10*K + WG[I]-48; I++;}
  *Q=K; *P=J; CNT1++; CNT2++; TCNT++;     TCNT=TCNT;  /* needed to use TCNT */
  P++; Q++;
  goto LP;

WEIGHTS:
  while (CNT1>0)
   {
    I++; if (WG[I]==',') I++;
    K=0; while ((WG[I]>='0') && (WG[I]<='9')) {K = 10*K + WG[I]-48; I++;}
    *R1=K; R1++;
    CNT1--;
   }
 if (WG[I]==',') I++;
 if (WG[I]!='&') goto NEWCLUSTER;

  while (CNT2>0)
   {
    I++; if (WG[I]==',') I++;
    K=0; while ((WG[I]>='0') && (WG[I]<='9')) {K = 10*K + WG[I]-48; I++;}
    *R2=K; R2++;
    CNT2--;
   }

 goto NEWCLUSTER;

}