import java.util.Map;
import java.util.TreeSet;


public class MaxFlow
{

	public static int getMaxFlow(Map<String, FlowNode> nodes, String source, String sink, int max)
	{
		for(FlowNode n : nodes.values())
		{
			n.reset();			
		}
		nodes.get(source).chg_type='S';
		nodes.get(source).chg_amt=Integer.MAX_VALUE;

		TreeSet<String> update_nodes=new TreeSet<String>();
		update_nodes.add(source);
		int to_sink=0;

		while(!update_nodes.isEmpty())
		{
			String update_str = update_nodes.first();
			update_nodes.remove(update_str);

			FlowNode n = nodes.get(update_str);

			if (update_str.equals(sink))
			{
				int amt=n.chg_amt;
				to_sink += amt;
				if (to_sink == max) return to_sink;
				String loc = sink;

				while(!loc.equals(source))
				{
					if (n.chg_type=='A')
					{
						nodes.get(n.chg_src).out_flows.get(loc).curr += amt;
					}
					if (n.chg_type=='D')
					{
						n.out_flows.get(n.chg_src).curr -= amt;
					}
					loc = n.chg_src;
					n = nodes.get(loc);
				}

				for(FlowNode n2 : nodes.values())
				{
					n2.chg_amt=0;
				}
				nodes.get(source).chg_amt=Integer.MAX_VALUE;
				update_nodes.clear();
				update_nodes.add(source);

			}
			else
			{
				for(String target : n.out_flows.keySet())
				{
					FlowAmount fa = n.out_flows.get(target);
					FlowNode target_n = nodes.get(target);

					if (target_n.chg_amt == 0)
					if (fa.curr < fa.max)
					{
						target_n.chg_type='A';
						target_n.chg_src=update_str;
						target_n.chg_amt=Math.min( fa.max - fa.curr, n.chg_amt);
						update_nodes.add(target);

					}

				}
				for(String target : nodes.keySet())
				{
					FlowNode target_n = nodes.get(target);
					FlowAmount fa = target_n.out_flows.get(update_str);

					if (fa != null)
					{
						if (fa.curr >0)
						if (!n.chg_src.equals(target))
						if (target_n.chg_amt==0)
						{
							target_n.chg_type='D';
							target_n.chg_src=update_str;
							target_n.chg_amt=Math.min( fa.curr, n.chg_amt);
							update_nodes.add(target);

						}

					}

				}


			}
		}

		return to_sink;

	}

}