Maximum Flow Algorithm - The Ford-Fulkerson Algorithm
Last Update: 25 August, 2009

Problem: The maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum.

Resource: Click Here To Download

 

My Code:

//C++ Code :  Max Flo

#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF  2147483647


/***************** Max Flow Algorithm***************
****************************************************/
const int maxINDX=102;
int flow[maxINDX][maxINDX],cap[maxINDX][maxINDX];
int path[maxINDX];
int src,dest;

int BFS(int node) {
	int i,item,cf;
	queue<int> q;
	for(i=1;i<=node;i++)
		path[i]=-2;// color i
	q.push(src);
	path[src]=-1;
	while(!q.empty()) {
		item=q.front();
		q.pop();
		if(item==dest) {
			i=dest;
			cf=INF;
			while(path[i]!=-1) {
				if(cf>flow[path[i]][i])
					cf=flow[path[i]][i];
				i=path[i];
			}
			return cf;
		}
		for(i=1;i<=node;i++) {
			if(flow[item][i]!=0 && path[i]==-2) {
				q.push(i);
				path[i]=item;
			}
		}
	} // end of while loo
	return 0;
}

int maxflow(int node) {
	int i,j,cf,totalflow=0;
	while((cf=BFS(node))!=0) {
		totalflow+=cf;
		i=dest;
		while(path[i]!=-1) {
			flow[path[i]][i]-=cf;
			flow[i][path[i]]+=cf;
			i=path[i];
		}
	}
	return totalflow;
}

void graph_initial(int node){
	int i,j;
	for(i=1;i<=node;i++){
		for(j=1;j<=node;j++) {
			cap[i][j]=0;
			flow[i][j]=0;
		}
	}

}

int main()
{
	//freopen("in.txt","rt",stdin)
	//freopen("out.txt","wt",stdout)

	int node,edge,a,b,c,i,resultedFlow;

	while(scanf("%d",&node)==1 && node!=0) {

		graph_initial(node);

		scanf("%d %d",&src,&dest);
		scanf("%d",&edge);

		for(i=1;i<=edge;i++) {
			scanf("%d %d %d",&a,&b,&c);
			cap[a][b]+=c;
			cap[b][a]+=c;
			flow[a][b]+=c;
			flow[b][a]+=c;
		}
		
		resultedFlow=maxflow(node);

		printf("%d\n",resultedFlow);
	}
	
// End of main function.......
return 0;
}


/***  Programmed by:
###########################
##   ORONNO   #############
## Team-:"DU-Gladiator"  ##
## CSEDU 12th Batch.  #####
###########################
Note: This program is not totally
useless. Because, at least, this
might be used as a bad example!!!!
**********************************/