// Basic preflow-push

#include <stdio.h>
#include <stdlib.h>

// Basic Definitions

#define oo 1000000000

// Declarations

int n;  // number of nodes
int e;  // number of edges
struct edge {
  int tail,head,capacity,flow,inverse; 
};
typedef struct edge edgeType;
edgeType *edgeTab;
int *firstEdge;  // Table indicating first in range of edges with a common tail

int *excessFlow,*height;

int min (int x, int y) {
    return x<y ? x : y;  // returns minimum of x and y
}

// Reading the input file and the main program

int tailThenHead(const void* xin, const void* yin)
/* Used in calls to qsort() and bsearch() for read_input_file() */
{
int result;
edgeType *x,*y;

x=(edgeType*) xin;
y=(edgeType*) yin;
result=x->tail - y->tail;
if (result!=0)
  return result;
else
  return x->head - y->head;
}

void read_input_file() {
    int a,b,c,i,j,numEdges;
    edgeType work;
    edgeType *ptr;
    FILE* input = fopen("mf.in","r");

    // read number of nodes and edges
    fscanf(input,"%d %d",&n,&e);
    edgeTab=(edgeType*) malloc(2*e*sizeof(edgeType));
    if (!edgeTab)
    {
      printf("edgeTab malloc failed\n");
      exit(0);
    }
    // read edge capacities
    numEdges=0;
    for (i=0; i<e; i++) {
        fscanf(input,"%d %d %d",&a,&b,&c);
        if (a<0 || a>=n || b<0 || b>=n || c<=0)
        {
          printf("Invalid input %d %d %d\n",a,b,c);
          exit(0);
        }
        edgeTab[numEdges].tail=a;
        edgeTab[numEdges].head=b;
        edgeTab[numEdges].capacity=c;
        numEdges++;
        edgeTab[numEdges].tail=b;
        edgeTab[numEdges].head=a;
        edgeTab[numEdges].capacity=0;
        numEdges++;
    }
    fclose(input);
    // sort edges
    qsort(edgeTab,numEdges,sizeof(edgeType),tailThenHead);
    // coalesce duplicates
    j=0;
    for (i=1; i<numEdges; i++)
      if (edgeTab[j].tail==edgeTab[i].tail
         && edgeTab[j].head==edgeTab[i].head)
         edgeTab[j].capacity+=edgeTab[i].capacity; 
      else
      {
        j++;
        edgeTab[j].tail=edgeTab[i].tail;
        edgeTab[j].head=edgeTab[i].head;
        edgeTab[j].capacity=edgeTab[i].capacity;
      }
    e=numEdges=j+1;
    // Set inverses
    for (i=0; i<numEdges; i++)
    {
      work.tail=edgeTab[i].head;
      work.head=edgeTab[i].tail;
      ptr=bsearch(&work,edgeTab,numEdges,sizeof(edgeType),tailThenHead);
      if (ptr==NULL)
      {
        printf("bsearch  %d failed\n",i);
        exit(0);
      }
      edgeTab[i].inverse=ptr-edgeTab;  // ptr arithmetic to get subscript
    }
    // For each vertex as a tail, determine first in range of edgeTab entries
    firstEdge=(int*) malloc((n+1)*sizeof(int));
    if (!firstEdge)
    {
      printf("malloc failed\n");
      exit(0);
    }
    j=0;
    for (i=0; i<n; i++)
    {
      firstEdge[i]=j;
      for ( ;
           j<numEdges && edgeTab[j].tail==i;
           j++)
        ;
    }
    firstEdge[n]=numEdges;
}

void dumpTables()
{
int i,j;

printf("  i height excess\n");
for (i=0;i<n;i++)
  printf("%3d %6d %6d\n",i,height[i],excessFlow[i]);

printf("  i   j capacity ...flow\n");
for (i=0;i<e;i++)
  if (edgeTab[i].capacity>0)
  {
    j=edgeTab[i].head;
    printf("%3d %3d %8d %7d\n",i,j,
      edgeTab[i].capacity,edgeTab[i].flow);
  }
}

initializePreflow()
{
int i,j;

for (i=0;i<n;i++)
{
  height[i]=0;
  excessFlow[i]=0;
}

for (i=0;i<e;i++)
  edgeTab[i].flow=0;

height[0]=n;

for (i=firstEdge[0];i<firstEdge[1];i++)
  if (edgeTab[i].capacity>0)
  {
    edgeTab[i].flow=edgeTab[i].capacity;
    edgeTab[edgeTab[i].inverse].flow=(-edgeTab[i].capacity);
    excessFlow[edgeTab[i].head]=edgeTab[i].capacity;
  }
}

int preflowPushLoop()
{
int foundOperation,didPush,i,j,k,dF,minHeight;

foundOperation=1;
while (foundOperation)
{
  foundOperation=0;
  for (i=1;i<n-1;i++)
    if (excessFlow[i]>0)
    {
      didPush=0;
      for (k=firstEdge[i];k<firstEdge[i+1];k++)
      {
        j=edgeTab[k].head;
        if (edgeTab[k].capacity-edgeTab[k].flow>0 &&
            height[i]==height[j]+1)
        {
          dF=min(excessFlow[i],edgeTab[k].capacity-edgeTab[k].flow);
          printf("debug:  pushing %d units from %d to %d\n",
            dF,i,j);
          edgeTab[k].flow+=dF;
          edgeTab[edgeTab[k].inverse].flow=(-edgeTab[k].flow);
          excessFlow[i]-=dF;
          excessFlow[j]+=dF;
          didPush=1;
          foundOperation=1;
          if (excessFlow[i]==0)
            break;
        }
      }
      if (!didPush)
      {
        minHeight=oo;
        for (k=firstEdge[i];k<firstEdge[i+1];k++)
        {
          j=edgeTab[k].head;
          if (edgeTab[k].capacity-edgeTab[k].flow>0 && height[j]<minHeight)
          {
            printf("debug:  (%d,%d) changed minHeight to %d\n",
              i,j,height[j]);
            minHeight=height[j];
          }
        }
        printf("debug:  lifting %d from %d to %d\n",
          i,height[i],1+minHeight);
        height[i]=1+minHeight;
        foundOperation=1;
      }
    }
  printf("debug:\n");
  dumpTables();
}
return excessFlow[n-1];
}

int main ()
{
int i,j;
read_input_file();
excessFlow=(int*) malloc(n*sizeof(int));
height=(int*) malloc(n*sizeof(int));
if (!excessFlow || !height)
{
  printf("malloc failed\n");
  exit(0);
}
initializePreflow();
printf("total flow is %d\n",preflowPushLoop());
printf("flows along edges:\n");
for (i=0; i<e; i++)
  if (edgeTab[i].flow>0)
    printf("%d->%d has %d\n",edgeTab[i].tail,
     edgeTab[i].head,edgeTab[i].flow);
free(height);
free(excessFlow);
free(edgeTab);
free(firstEdge);
return 0;
}