// Derived from 
// http://www.aduni.org/courses/algorithms/handouts/Reciation_09.html#25630

// The Ford-Fulkerson Algorithm in C

#include <stdio.h>

// Basic Definitions

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 1000
#define oo 1000000000

// Declarations

int n;  // number of nodes
int e;  // number of edges
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES];     // flow matrix
int color[MAX_NODES]; // needed for breadth-first search               
int pred[MAX_NODES];  // array to store augmenting path

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

// A Queue for Breadth-First Search

int head,tail;
int q[MAX_NODES+2];

void enqueue (int x) {
    q[tail] = x;
    tail++;
    color[x] = GRAY;
}

int dequeue () {
    int x = q[head];
    head++;
    color[x] = BLACK;
    return x;
}

// Breadth-First Search for an augmenting path

int bfs (int start, int target) {
    int u,v;
    for (u=0; u<n; u++) {
        color[u] = WHITE;
    }   
    head = tail = 0;
    enqueue(start);
    pred[start] = -1;
    while (head!=tail) {
        u = dequeue();
        // Search all adjacent white nodes v. If the capacity
        // from u to v in the residual network is positive,
        // enqueue v.
        for (v=0; v<n; v++) {
            if (color[v]==WHITE && capacity[u][v]-flow[u][v]>0) {
                enqueue(v);
                pred[v] = u;
            }
        }
    }
    // If the color of the target node is black now,
    // it means that we reached it.
    return color[target]==BLACK;
}

// Ford-Fulkerson Algorithm

int max_flow (int source, int sink) {
    int i,j,u;
    // Initialize empty flow.
    int max_flow = 0;
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            flow[i][j] = 0;
        }
    }
    // While there exists an augmenting path,
    // increment the flow along this path.
    while (bfs(source,sink)) {
        // Determine the amount by which we can increment the flow.
        int increment = oo;
        for (u=sink; pred[u]!=(-1); u=pred[u]) {
            increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]);
        }
        // Now increment the flow.
        for (u=sink; pred[u]!=(-1); u=pred[u]) {
            flow[pred[u]][u] += increment;
            flow[u][pred[u]] -= increment;  // Reverse in residual
        }
        // Path trace
        for (u=sink; pred[u]!=(-1); u=pred[u]) {
            printf("%d<-",u);
        }
        printf("%d adds %d incremental flow\n",source,increment);
        max_flow += increment;
    }
    // No augmenting path anymore. We are done.
    return max_flow;
}

// Reading the input file and the main program

void read_input_file() {
    int a,b,c,i,j;
    FILE* input = fopen("mf.in","r");
    // read number of nodes and edges
    fscanf(input,"%d %d",&n,&e);
    // initialize empty capacity matrix 
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            capacity[i][j] = 0;
        }
    }
    // read edge capacities
    for (i=0; i<e; i++) {
        fscanf(input,"%d %d %d",&a,&b,&c);
        capacity[a][b] += c; // Could have parallel edges
    }
    fclose(input);
}

int main () {
    int i,j;
    read_input_file();
    printf("total flow is %d\n",max_flow(0,n-1));
    printf("flows along edges:\n");
    for (i=0; i<n; i++)
      for (j=0; j<n; j++)
        if (flow[i][j]>0)
          printf("%d->%d has %d\n",i,j,flow[i][j]);
    return 0;
}