/* 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,4,#9,9,  -2,3,#7,  -3,4,6,#4,5,   -4,5,#13,  -5,6,#12]"; */

  /*   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,#7,7,&3,4,  -2,3,8,#5,2,&1,2,   -3,2,10,#3,7,&0,1,/"
            "-4,5,7,#4,4,&3,1,  -5,6,#2,&3,  -6,8,9,10,#2,2,3,&0,1,2,/"
            "-7,1,#4,&,1,  -8,5,7,9,#2,3,4,&0,0,2,   -9,10,#3,&3]";  */

    WG[] = "[-1,2,4,#5,6,&5,4,  -2,6,#6,&6,/"
              "-3,1,2,#4,2,&1,0,   -4,3,5,#3,3,&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+1; K++) {if (A[K]>Nobj) Nobj=A[K]; if (B[K]>Nobj) Nobj=B[K];}
  A[Npairs+1]=Nobj;   B[Npairs+1]=Nobj+1;
 printf("%d directed links,    %d largest node label\n",Npairs,Nobj);
 for (K=1; K<=Npairs+1; K++) printf("%3d,",K); puts("");
 for (K=1; K<=Npairs+1; K++) printf("%3d,",A[K]); puts("");
 for (K=1; K<=Npairs+1; K++) printf("%3d,",B[K]); puts("");
 for (K=1; K<=Npairs+1; K++) printf("%3d,",CAP[K]); puts("");
 for (K=1; K<=Npairs+1; K++) printf("%3d,",FLOW[K]); puts("");

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

 SORTBA(A,B,CAP,FLOW,Ar,Br,Cr,Fr,Npairs);
 /* Br[0]=A[1]; */
 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;
                                            /* printf("Npairs=%d\n",Npairs); */
LP:
 while (A[K]==A[K-1]) K--;
 INDEXA[A[K]]=K;                           /* printf("%d(%d) ",A[K],K); */  
 if (K>1) {K--; goto LP;}
 return;
}

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

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


 while (K) {{if (Br[K]!=Br[K-1]) INDEXBr[Br[K]]=K;} K--;}
 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;  P++; Q++;
 for (K=1; K<=Npairs; K++) {BA[K] = *Q*10000 + *P; P++; Q++;}
 P=C; Q=F;  P++; Q++;
 for (K=1; K<=Npairs; K++) {CF[K] = *P*10000 + *Q; P++; Q++;}

 for (I=1; 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;  P++; Q++;
 for (K=1; K<=Npairs; K++) {*P = BA[K]%10000; *Q = BA[K]/10000; P++; Q++;}
 *P=*Q=0;
 P=Cr; Q=Fr;  P++; Q++;
 for (K=1; K<=Npairs; K++) {*P = CF[K]/10000; *Q = CF[K]%10000; P++; Q++;}
 *P=*Q=0;
 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");

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

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

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

 puts("total flow in  (node)  total flow out");

  printf("x");  K=1;

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

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

  printf("Flow through digraph entered at node 1 and exited at node %d\n",Nobj);
  printf("Distribution of flow inside digraph:\n");
  printf("Total amount of flow from source to destination = 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;

 *P=*Q=*R1=*R2=I=0;    P++; Q++; R1++; R2++;
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;

}