﻿ Tips And Tutorial - Presented by Oneous!

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!!!!
**********************************/``````