#include <stdio.h>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 1000
#define oo 1000000000
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
}
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;
}
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;
}

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=n-1; pred[u]>=0; u=pred[u]) {
	    increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]);
	}
        // Now increment the flow.
	for (u=n-1; pred[u]>=0; u=pred[u]) {
	    flow[pred[u]][u] += increment;
	    flow[u][pred[u]] -= increment;
	}
	max_flow += increment;
    }
    // No augmenting path anymore. We are done.
    return max_flow;
}

void read_input_file() {
    int a,b,c,i,j;
    FILE* input = fopen("data.txt","r");
    // read number of nodes and edges
    fscanf(input,"%d %d",&n,&e);
    printf("\nNumber of Vertices : %d   Edges : %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;
	printf("\nA : %d  B : %d  Capacity : %d",a,b,c);
    }
    fclose(input);
}

int main () {
    read_input_file();
    printf("\nPlease enter Source(s) and Sink(t) :\n");
    int s=0,t=n-1;
    scanf("%d %d",&s,&t);
    printf("\nMax Flow : %d\n",max_flow(s,t));
    return 0;
}

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

#define infinity 9999
#define LIMIT 10
#define NIL -1
#define PERMANENT 1
#define TEMPORARY 0

struct edge
{
      int v;
      int u;
};

int n;	
int predecessor[LIMIT];
int adjacency_matrix[LIMIT][LIMIT];
int length[LIMIT];
int status[LIMIT];

int min_temp();
void new_graph();
void maketree(int root_var, struct edge tree[LIMIT]);

int main()
{
      int tree_weight = 0; 
      int count, root;
      struct edge tree[LIMIT];
      new_graph();
      printf("\nEnter Root Vertex:\t");
      scanf("%d", &root);
      maketree(root, tree);
      printf("Enter Edges of the Spanning Tree:\n");
      for(count = 1; count <= n - 1; count++)
      {
            printf("%d->", tree[count].u);
            printf("%d\n", tree[count].v);
            tree_weight = tree_weight + adjacency_matrix[tree[count].u][tree[count].v];
      }
      printf("Spanning Tree Weight:\t%d\n", tree_weight);
      return 0;
}

void new_graph()
{
      int count, LIMIT_edges, origin, destination, weight;
      printf("Enter Number of Vertices:\t");
      scanf("%d", &n);
      LIMIT_edges = n * (n - 1) /2;
      for(count = 1; count <= LIMIT_edges; count++)
      {
            printf("Enter Co- Ordinates of Edge No. %d(-1 -1 to quit):\n",count);
            printf("Enter Origin Vaue:\t");
            scanf("%d", &origin);
            printf("Enter Destination Vaue:\t");
            scanf("%d", &destination);
            if((origin == -1) && (destination == -1))
            {
                  break;
            }
            printf("Enter Weight of this Edge:\t");
            scanf("%d", &weight);
            if(destination < 0 || destination >= n || origin < 0 || origin >= n)
            {
                  printf("Invalid Edge\n");
                  count--;
            }
            else
            {
                  adjacency_matrix[origin][destination] = weight;
                  adjacency_matrix[destination][origin] = weight;
            }
      }
}

void maketree(int root_var, struct edge tree[LIMIT])
{	
      int current, count;
      int temp = 0;
      for(count = 0; count < n; count++)
      {
            predecessor[count] = NIL;
            length[count] = infinity;
            status[count] = TEMPORARY;
      }
      length[root_var] = 0;
      while(1)
      {
            current = min_temp();
            if(current == NIL) 
            {
                  if(temp == n - 1)
                  {
                        return;
                  }
                  else	
                  {
                        printf("No Spanning Tree is Possible because Graph is disconnected\n");
                        exit(1);
                  }
            }
            status[current] = PERMANENT;
            if(current != root_var)
            {
                  count++;
                  tree[temp].u = predecessor[current];
                  tree[temp].v = current;
            }
            for(count = 0; count < n; count++)
            {
                  if(adjacency_matrix[current][count] > 0 && status[count] == TEMPORARY)
                  {
                        if(adjacency_matrix[current][count] < length[count])
                        {
                              predecessor[count] = current;
                              length[count] = adjacency_matrix[current][count];
                        }
                  }
            }
      }
}

int min_temp()
{
      int count;
      int min = infinity;
      int x = -1;
      for(count = 0; count < n; count++)
      {
            if(status[count] == TEMPORARY && length[count] < min)
            {
                  min = length[count];
                  x = count;
            }
      }
      return x;
}