/*
 * e_032_max_flow_ford_fulkerson.cpp
 *
 *  Created on: May 16, 2015
 *      Author: Marius
 */

#include <iostream>
using namespace std;
#include <fstream>
#include <queue>
#include <list>
#include <vector>
#include <string>
#include <algorithm>

namespace e_032_max_flow_ford_fulkerson_nms
{
	struct Edge
	{
		int u, v; // edge u to v
		int c; // the capacity
		int dir; // direction: forward (1) or backward (-1) edge
		Edge* re; // pointer to the reverse edge in the graph
	};

	int find_max_flow_ford_fulkerson(int N, vector<vector<Edge*>>& adj_list)
	{
		int max_flow = 0;

		list<int> Q;
		list<Edge*> QN; // the list of non-saturate edges u-N
		vector<char> touched_queue;
		vector<Edge*> parent_edges;
		touched_queue.resize(N + 1);
		parent_edges.resize(N + 1);
		bool has_s2t_path = true;
		while (has_s2t_path)
		{
			//no node on the path at the beginning
			Q.clear();
			QN.clear();
			std::fill(touched_queue.begin(), touched_queue.end(), 0);
			for (auto& ep : parent_edges)
				ep = 0;
			//find a path from source to sink in the residual graph
			//only edges with positive capacities should be included in the path
			Q.push_back(1);
			touched_queue[1] = 1;
			while (!Q.empty())
			{
				int u = Q.front();
				Q.pop_front();
				for (auto& e : adj_list[u])
				{
					int v = e->v;
					//not already in queue and an edge with positive capacity
					if (!touched_queue[v] && e->c > 0)
					{
						if (v != N)
						{			
							//put the node in the list
							Q.push_back(v);
							touched_queue[v] = 1;
							parent_edges[v] = e;
						}
						else
						{
							//We want a complete BFS with non-saturated edges, 
							//excluding the final node, so we don't add the final node into the BFS.
							//We save the parent node into a list.
							QN.push_back(e);							
						}
					}
				}
			}

			//parse the list of nodes with u-N non-saturated edges
			for (auto& en : QN)
			{
				int min_capacity = en->c; //this capacity is non-zero by design
				int node = en->u;				
				while (node != 1)
				{
					Edge* e = parent_edges[node];
					min_capacity = min(min_capacity, e->c);
					//check if the capacity of the current node was not already saturated by
					// another QN edge. if so, break
					if (min_capacity == 0) break;
					//go to the parent node
					node = e->u;
				}
				
				if (min_capacity > 0)
				{
					//we have a non-saturated path from N to 1
					max_flow += min_capacity; //update the max flow
					
					//update the capacity of edges in the residual graph
					en->c -= min_capacity;
					//also update the reverse edge
					en->re->c += min_capacity;
					
					node = en->u;
					while (node != 1)
					{
						//update the capacity of edges in the residual graph
						Edge* e = parent_edges[node];
						e->c -= min_capacity;
						//also update the reverse edge
						e->re->c += min_capacity;
						//go to the parent node
						node = e->u;
					}
				}
			}
			
			if (QN.size() == 0) has_s2t_path = false;					
		}

		return max_flow;
	}
}

// int e_032_max_flow_ford_fulkerson()
int main()
{
	using namespace e_032_max_flow_ford_fulkerson_nms;

	string in_file = "maxflow.in";
	string out_file = "maxflow.out";

	int N, M;
	vector<vector<Edge*>> adj_list;

	ifstream ifs(in_file.c_str());
	if (!ifs.is_open())
	{
		cout << "Input file not found" << endl;
		return -1; // no input file
	}
	ifs >> N >> M;

	adj_list.resize(N + 1);

	for (int m = 1; m <= M; m++)
	{
		//create the forward and it's backward edge
		Edge* e = new Edge;
		Edge* re = new Edge;

		ifs >> e->u >> e->v >> e->c;
		e->dir = 1;
		e->re = re;

		re->u = e->v;
		re->v = e->u;
		re->c = 0;
		re->dir = -1;
		re->re = e;

		adj_list[e->u].push_back(e);
		adj_list[e->v].push_back(re);
	}

	ifs.close();

	int max_flow = find_max_flow_ford_fulkerson(N, adj_list);
	ofstream ofs(out_file.c_str());
	ofs << max_flow;
	ofs.close();

	//release the memory
	for (int u = 1; u <= N; u++)
		for (vector<Edge*>::iterator it = adj_list[u].begin(); it != adj_list[u].end(); it++)
			delete *it;

	return 0;
}