/*
 * 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;
		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();
			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;
			bool found_destination = false;
			while (!Q.empty() && !found_destination)
			{
				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)
					{
						//put the node in the list
						Q.push_back(v);
						touched_queue[v] = 1;
						parent_edges[v] = e;

						//check if we have reached the final node
						if (v == N)
						{
							found_destination = true;
							break;
						}
					}
				}
			}

			if (found_destination)
			{
				// we have a path from source to sink
				// update the residual graph
				//
				// parse the path we have found from sink to source, via parent edges
				// and find the minimum capacity
				int min_capacity = parent_edges[N]->c + 1;
				int node = N;
				while (node != 1)
				{
					Edge* e = parent_edges[node];
					min_capacity = min(min_capacity, e->c);
					node = e->u;
				}
				//increment the flow value
				max_flow += min_capacity;

				//update the capacity of edges in the residual graph
				node = N;
				while (node != 1)
				{
					Edge* e = parent_edges[node];
					e->c -= min_capacity;
					//also update the reverse edge
					e->re->c += min_capacity;
					node = e->u;
				}
			}
			else
				has_s2t_path = false; //no more paths from s to t
		}

		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;
}