finding maximum flow (ford-fulkerson)

findMaxFlow.cpp

int findMaxFlow()
{
	int totalFlow = 0;
	while(true)
	{
		int flow[MAX_N] = { }, prev[MAX_N] = { };
		bool seen[MAX_N] = { };
		flow[S] = inf;

		int maxFlow, maxLoc;
		while(true)
		{
			maxLoc = -1;
			maxFlow = 0;
			for(int i = 1; i <= N; i++)
			{
				if(!seen[i] && flow[i] > maxFlow)
				{
					maxFlow = flow[i];
					maxLoc = i;
				}
			}

			if(maxLoc == -1) break;
			if(maxLoc == T)	break;

			seen[maxLoc] = true;

			for(int i = 1; i <= N; i++)
			{
				if(flow[i] < min(maxFlow, cap[maxLoc][i])) 
				{
					flow[i] = min(maxFlow, cap[maxLoc][i]);
					prev[i] = maxLoc;
				}
			}
		}

		if(maxLoc == -1) break;

		int pathCap = flow[T];
		totalFlow += pathCap;

		int curNode = T;
		while(curNode != S)
		{
			int prevNode = prev[curNode];

			cap[prevNode][curNode] -= pathCap;
			cap[curNode][prevNode] += pathCap;

			curNode = prevNode;
		}
	}
	return totalFlow;
}