#pragma once
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct NODE
{
	int h;
	int e;
	vector<int> f;
	vector<int> c;
	vector<int> inc;
};

class FLOW
{
	std::vector<NODE> arr;
	std::vector<char> name;
	std::vector<int> extra;
	int start = -1;
	int finish = -1;
	void push(int, int);
	void relabel(int);
	void init();
	bool discharge(int);
	/*int leveldiff(int);
	void isextra(int);*/
public:
	void input(fstream&);
	int calc_maxflow();
};

bool FLOW :: discharge(int u)
{
	bool lifted = false;
	while (arr[u].e > 0)
	{
		int i;
		for (i = 0; i < arr[u].inc.size() && arr[u].e > 0; ++i)
		{
			if (arr[u].h == arr[arr[u].inc[i]].h + 1 && arr[u].c > arr[u].f)
			{
				push(u, arr[u].inc[i]);
			}
		}
		if (i == arr[u].inc.size() && arr[u].e > 0)
		{
			relabel(u);
			lifted = true;
		}
	}
	extra.erase(std::remove(extra.begin(), extra.end(), u), extra.end());
	return lifted;
}

//void FLOW::isextra(int u)
//{
//	bool flaq = false;
//	for (int i = 0; i < arr[u].c.size(); ++i)
//	{
//		if (arr[u].c != arr[u].f)
//		{
//			flaq = true;
//			break;
//		}
//	}
//	if (!flaq)
//		extra.erase(std::remove(extra.begin(), extra.end(), u), extra.end());
//}

//int FLOW::leveldiff(int u)
//{
//	for (int i = 0; i < arr[u].inc.size(); ++i)
//	{
//		if (arr[u].h > arr[arr[u].inc[i]].h && arr[u].c[i] != arr[u].f[i])
//			return arr[u].inc[i];
//	}
//	return -1;
//}

void FLOW::push(int u, int v)
{
	int num = 0;
	for (int i = 0; i < arr[u].inc.size(); ++i)
	{
		if (arr[u].inc[i] == v)
		{
			num = i;
			break;
		}
	}
	int d = ((arr[u].c[num] - arr[u].f[num]) < arr[u].e) ? (arr[u].c[num] - arr[u].f[num]) : arr[u].e;
	arr[u].e -= d;
	if (!arr[u].e)
		extra.erase(std::remove(extra.begin(), extra.end(), u), extra.end());
	arr[u].f[num] += d;
	arr[v].e += d;
	if (arr[v].e && v != finish && v != start && !count(extra.begin(), extra.end(), v))
		extra.push_back(v);
}

void FLOW::relabel(int u)
{
	int min = arr.size() * 2;
	for (int i = 0; i < arr[u].inc.size(); ++i)
	{
		if (arr[arr[u].inc[i]].h < min && arr[u].f[i] != arr[u].c[i])
			min = arr[arr[u].inc[i]].h;
	}
	arr[u].h = min + 1;
}

void FLOW::init()
{
	for (int i = 0; i < arr.size(); ++i)
	{
		if (i == start)
		{
			arr[i].h = arr.size();
			for (int j = 0; j < arr[i].inc.size(); ++j)
			{
				arr[arr[i].inc[j]].e = arr[i].c[j];
				arr[i].f[j] = arr[i].c[j];
				if (arr[i].inc[j] != start && arr[i].inc[j] != finish)
					extra.push_back(arr[i].inc[j]);
			}
		}
		else
		{
			arr[i].h = 0;
		}
	}
}

int FLOW::calc_maxflow()
{
	if (start == -1 || finish == -1)
	{
		cout << "Error! Incorrect input data.\n";
		return -1;
	}
	else
	{
		init();
		while (extra.size())
		{
			discharge(extra[0]);
		}
		return arr[finish].e;
	}
}

void FLOW::input(fstream & file)
{
	while (!file.eof())
	{
		bool flaq = false;
		int first, second;
		string str1, str2, str3;
		std::getline(file, str1, ' ');
		for (int i = 0; i < name.size(); ++i)
		{
			if (name[i] == str1[0])
			{
				flaq = true;
				first = i;
			}
		}
		if (!flaq)
		{
			if (str1[0] == 'S')
				start = name.size();
			first = name.size();
			name.push_back(str1[0]);
			arr.push_back(NODE());
		}
		flaq = false;
		std::getline(file, str2, ' ');
		for (int i = 0; i < name.size(); ++i)
		{
			if (name[i] == str2[0])
			{
				flaq = true;
				second = i;
			}
		}
		if (!flaq)
		{
			if (str2[0] == 'T')
				finish = name.size();
			second = name.size();
			name.push_back(str2[0]);
			arr.push_back(NODE());
		}
		std::getline(file, str3, '\n');
		arr[first].inc.push_back(second);
		arr[first].c.push_back(stoi(str3));
		arr[second].inc.push_back(first);
		arr[second].c.push_back(stoi(str3));
		arr[first].f.push_back(0);
		arr[second].f.push_back(0);
	}
}