Language: C++

#pragma once
#ifndef NETWORK_HPP
#define NETWORK_HPP

#include <cinttypes>
#include <iostream>
#include <vector>
#include <limits>
#include <memory>



const std::size_t InfiniteSize = 
		std::numeric_limits<std::size_t>::max();

template<typename T>
class Network
{
protected:
	virtual void setSource(std::size_t source) = 0;
	virtual void setTarget(std::size_t target) = 0;
	virtual void addBareEdge(
		std::size_t from, std::size_t to, T capacity) = 0;

	class InternalIterator;
public:
	class Iterator;

	virtual std::size_t VerticeCount() = 0;
	virtual std::size_t EdgeCount() = 0;
	virtual std::size_t Source() = 0;
	virtual std::size_t Target() = 0;

	virtual void ClearFlow() = 0;

	virtual Iterator IterateOutgoingEdgesAt(std::size_t from) = 0;
	virtual Iterator IterateIncomingEdgesAt(std::size_t to) = 0;

	virtual ~Network() = default;
};

template<typename T>
class Network<T>::InternalIterator
{
protected:
	virtual void advance() = 0;
	virtual bool ended() = 0;
	virtual std::unique_ptr<InternalIterator> copy() = 0;

	friend class Iterator;

public:
	virtual std::size_t Source() = 0;
	virtual std::size_t Target() = 0;
	virtual T Capacity() = 0;
	virtual T Flow() = 0;

	virtual void AddFlow(T amount) = 0;

	virtual ~InternalIterator() = default;
};

template<typename T>
class Network<T>::Iterator
{
	std::unique_ptr<InternalIterator> internal_;

public:
	Iterator(std::unique_ptr<InternalIterator> internal);
	Iterator(Iterator& other);
	Iterator(Iterator&& other) = default;
	Iterator& operator=(Iterator& other);
	Iterator& operator=(Iterator&& other) = default;

	InternalIterator* operator->();

	Iterator& operator++();
	Iterator operator++(int);

	operator bool();
};

template<typename T>
std::ostream& operator<<(std::ostream& out, Network<T>& network);

#include "Network.tpp"

#endif // NETWORK_HPP
#include "Network.hpp"

template<typename T>
std::ostream& operator<<(std::ostream& out, Network<T>& network)
{
	out << "digraph G" << std::endl;
	out << "{" << std::endl;
	out << "\t" << network.Source() << " [color=green]" << std::endl;
	out << "\t" << network.Target() << " [shape=box]" << std::endl;
	for (std::size_t i = 0; i < network.VerticeCount(); ++i)
	{
		auto it = network.IterateOutgoingEdgesAt(i);
		while (it)
		{
			out << "\t" << it->Source() << " -> " << it->Target() << " ";
			out << "[label=\"";
			out << it->Flow();
			out << "/";
			out << it->Capacity();
			out << "\"]" << std::endl;

			++it;
		}
	}
	out << "}" << std::endl;
	return out;
}


template<typename T>
Network<T>::Iterator::Iterator(std::unique_ptr<InternalIterator> internal)
	: internal_(std::move(internal))
{

}

template<typename T>
Network<T>::Iterator::Iterator(Iterator& other)
	: internal_(other.internal_->copy())
{

}

template<typename T>
auto Network<T>::Iterator::operator=(Iterator& other)
	-> Iterator&
{
	internal_ = other.internal_.copy();
	return *this;
}

template<typename T>
auto Network<T>::Iterator::operator->()
	-> InternalIterator*
{
	return &*internal_;
}

template<typename T>
auto Network<T>::Iterator::operator++()
	-> Iterator&
{
	internal_->advance();
	return *this;
}

template<typename T>
auto Network<T>::Iterator::operator++(int)
	-> Iterator
{
	Iterator copy(internal_->copy());
	++*this;
	return copy;
}

template<typename T>
Network<T>::Iterator::operator bool()
{
	return !internal_->ended();
}
#pragma once
#ifndef EDGELISTNETWORK_HPP
#define EDGELISTNETWORK_HPP

#include <cinttypes>
#include <vector>
#include "Network.hpp"


template<typename T>
class EdgeListNetwork : public Network<T>
{
protected:
	std::size_t verticeCount_;
	std::size_t edgeCount_;

	std::size_t source_;
	std::size_t target_;

	//Edge properties
	std::vector<std::size_t> from_;
	std::vector<std::size_t> to_;
	std::vector<T> capacity_;
	std::vector<T> flow_;

	std::vector<std::size_t> firstEdgeFrom_;
	std::vector<std::size_t> nextEdgeFrom_;

	std::vector<std::size_t> firstEdgeTo_;
	std::vector<std::size_t> nextEdgeTo_;

	template<template<typename> class ConcreteNetwork, typename T1>
	friend class NetworkBuilder;

	explicit EdgeListNetwork(std::size_t vertices);

	void setSource(std::size_t source) override;
	void setTarget(std::size_t target) override;
	void addBareEdge(
		std::size_t from, std::size_t to, T capacity) override;

public:
	class InternalIterator;

	std::size_t VerticeCount() override;
	std::size_t EdgeCount() override;
	std::size_t Source() override;
	std::size_t Target() override;

	void ClearFlow() override;

	typename Network<T>::Iterator IterateOutgoingEdgesAt(std::size_t from) override;
	typename Network<T>::Iterator IterateIncomingEdgesAt(std::size_t to) override;
};


template<typename T>
class EdgeListNetwork<T>::InternalIterator : public Network<T>::InternalIterator
{
	std::size_t edgeIndex_;
	EdgeListNetwork<T>* network_;
	bool outgoing_;
	bool ended_;

	InternalIterator(std::size_t index, EdgeListNetwork<T>* network, bool outgoing);

	void advance() override;
	bool ended() override;
	std::unique_ptr<typename Network<T>::InternalIterator> copy() override;

	friend class EdgeListNetwork<T>;

public:
	std::size_t Source() override;
	std::size_t Target() override;
	T Capacity() override;
	T Flow() override;

	void AddFlow(T amount) override;
};

#include "EdgeListNetwork.tpp"

#endif // EDGELISTNETWORK_HPP
#include "EdgeListNetwork.hpp"




template<typename T>
EdgeListNetwork<T>::EdgeListNetwork(std::size_t vertices)
	: verticeCount_(vertices), edgeCount_(0),
		firstEdgeFrom_(vertices, InfiniteSize),
		firstEdgeTo_(vertices, InfiniteSize)
{

}

template<typename T>
void EdgeListNetwork<T>::setSource(std::size_t source)
{
	source_ = source;
}

template<typename T>
void EdgeListNetwork<T>::setTarget(std::size_t target)
{
	target_ = target;
}

template<typename T>
void EdgeListNetwork<T>::addBareEdge(
	std::size_t from, std::size_t to, T capacity)
{
	if (firstEdgeFrom_[from] != InfiniteSize)
		nextEdgeFrom_.push_back(firstEdgeFrom_[from]);
	else
		nextEdgeFrom_.push_back(edgeCount_);

	if (firstEdgeTo_[to] != InfiniteSize)
		nextEdgeTo_.push_back(firstEdgeTo_[to]);
	else
		nextEdgeTo_.push_back(edgeCount_);

	firstEdgeFrom_[from] = edgeCount_;
	firstEdgeTo_[to] = edgeCount_;
	from_.push_back(from);
	to_.push_back(to);
	capacity_.push_back(capacity);
	flow_.push_back(T(0));
	++edgeCount_;
}

template<typename T>
std::size_t EdgeListNetwork<T>::VerticeCount()
{
	return verticeCount_;
}

template<typename T>
std::size_t EdgeListNetwork<T>::EdgeCount()
{
	return edgeCount_;
}

template<typename T>
std::size_t EdgeListNetwork<T>::Source()
{
	return source_;
}

template<typename T>
std::size_t EdgeListNetwork<T>::Target()
{
	return target_;
}

template<typename T>
void EdgeListNetwork<T>::ClearFlow()
{
	flow_.assign(flow_.size(), 0);
}

template<typename T>
auto EdgeListNetwork<T>::IterateOutgoingEdgesAt(std::size_t from)
	-> typename Network<T>::Iterator
{
	return typename Network<T>::Iterator(
		std::unique_ptr<InternalIterator>(
			new InternalIterator(firstEdgeFrom_[from], this, true)));
}

template<typename T>
auto EdgeListNetwork<T>::IterateIncomingEdgesAt(std::size_t to)
	-> typename Network<T>::Iterator
{
	return typename Network<T>::Iterator(
		std::unique_ptr<InternalIterator>(
			new InternalIterator(firstEdgeTo_[to], this, false)));
}

template<typename T>
EdgeListNetwork<T>::InternalIterator::InternalIterator(std::size_t index,
	EdgeListNetwork<T>* network, bool outgoing)
		: edgeIndex_(index), network_(network),
			outgoing_(outgoing),
			ended_(index == InfiniteSize)
{

}

template<typename T>
T EdgeListNetwork<T>::InternalIterator::Capacity()
{
	return network_->capacity_[edgeIndex_];
}

template<typename T>
T EdgeListNetwork<T>::InternalIterator::Flow()
{
	return network_->flow_[edgeIndex_];
}

template<typename T>
std::size_t EdgeListNetwork<T>::InternalIterator::Source()
{
	return network_->from_[edgeIndex_];
}

template<typename T>
std::size_t EdgeListNetwork<T>::InternalIterator::Target()
{
	return network_->to_[edgeIndex_];
}

template<typename T>
void EdgeListNetwork<T>::InternalIterator::AddFlow(T amount)
{
	network_->flow_[edgeIndex_] += amount;
	network_->flow_[edgeIndex_ ^ 1] -= amount;
}

template<typename T>
void EdgeListNetwork<T>::InternalIterator::advance()
{
	auto nextIndex = outgoing_ ? 
		network_->nextEdgeFrom_[edgeIndex_] 
			: network_->nextEdgeTo_[edgeIndex_];

	if (edgeIndex_ == nextIndex)
		ended_ = true;
	edgeIndex_ = nextIndex;
}

template<typename T>
bool EdgeListNetwork<T>::InternalIterator::ended()
{
	return ended_;
}

template<typename T>
std::unique_ptr<typename Network<T>::InternalIterator>
	EdgeListNetwork<T>::InternalIterator::copy()
{
	std::unique_ptr<InternalIterator> copy(
			new InternalIterator(edgeIndex_, network_, outgoing_));
	copy->ended_ = ended_;
	return copy;
}
#pragma once
#ifndef NETWORKBUILDER_HPP
#define NETWORKBUILDER_HPP

#include "Network.hpp"
#include <memory>


template<template<typename> class ConcreteNetwork, typename T>
class NetworkBuilder
{
	std::size_t source_;
	std::size_t target_;
	std::vector<std::vector<T>> adjacencyMatrix_;
	using OwnType = NetworkBuilder<ConcreteNetwork, T>;

public:
	NetworkBuilder& Initialize(std::size_t vertices);
	NetworkBuilder& SetSource(std::size_t source);
	NetworkBuilder& SetTarget(std::size_t target);
	NetworkBuilder& AddCapacity(
		std::size_t from, std::size_t to, T capacity);

	std::unique_ptr<ConcreteNetwork<T>> Finalize();
};

#include "NetworkBuilder.tpp"

#endif // NETWORKBUILDER_HPP
#include "NetworkBuilder.hpp"


template<template<typename> class ConcreteNetwork, typename T>
auto NetworkBuilder<ConcreteNetwork, T>::Initialize(std::size_t vertices)
	-> OwnType&
{
	adjacencyMatrix_.assign(vertices, std::vector<T>(vertices, T(0)));
	return *this;
}

template<template<typename> class ConcreteNetwork, typename T>
auto NetworkBuilder<ConcreteNetwork, T>::SetSource(std::size_t source)
	-> OwnType&
{
	source_ = source;
	return *this;
}

template<template<typename> class ConcreteNetwork, typename T>
auto NetworkBuilder<ConcreteNetwork, T>::SetTarget(std::size_t target)
	-> OwnType&
{
	target_ = target;
	return *this;
}

template<template<typename> class ConcreteNetwork, typename T>
auto NetworkBuilder<ConcreteNetwork, T>::AddCapacity(
	std::size_t from, std::size_t to, T capacity)
	-> OwnType&
{
	adjacencyMatrix_[from][to] += capacity;
	return *this;
}

template<template<typename> class ConcreteNetwork, typename T>
auto NetworkBuilder<ConcreteNetwork, T>::Finalize()
	-> std::unique_ptr<ConcreteNetwork<T>>
{
	std::unique_ptr<ConcreteNetwork<T>>
		network(new ConcreteNetwork<T>(adjacencyMatrix_.size()));
	network->setSource(source_);
	network->setTarget(target_);
	for (std::size_t i = 0; i < adjacencyMatrix_.size(); ++i)
	{
		for (std::size_t j = i + 1; j < adjacencyMatrix_[i].size(); ++j)
		{
			if (adjacencyMatrix_[i][j] <= 0 && adjacencyMatrix_[j][i] <= 0)
				continue;

			network->addBareEdge(i, j, adjacencyMatrix_[i][j]);
			network->addBareEdge(j, i, adjacencyMatrix_[j][i]);
		}
	}
	return network;
}
#pragma once
#ifndef MAXFLOWALGORITHM_HPP
#define MAXFLOWALGORITHM_HPP

#include "Network.hpp"


template<typename T>
class MaxFlowAlgorithm
{
protected:
	std::shared_ptr<Network<T>> network_;

public:
	virtual void Initialize(std::shared_ptr<Network<T>> network);

	std::shared_ptr<Network<T>> GetNetwork();

	T GetFlow();

	virtual void Calculate() = 0;
};

#include "MaxFlowAlgorithm.tpp"

#endif // MAXFLOWALGORITHM_HPP
#include "MaxFlowAlgorithm.hpp"

template<typename T>
void MaxFlowAlgorithm<T>::Initialize(std::shared_ptr<Network<T>> network)
{
	network_ = network;
}

template<typename T>
std::shared_ptr<Network<T>> MaxFlowAlgorithm<T>::GetNetwork()
{
	return network_;
}

template<typename T>
T MaxFlowAlgorithm<T>::GetFlow()
{
	T flow = 0;

	for (auto it = network_->IterateOutgoingEdgesAt(network_->Source()); it; ++it)
	{
		flow += it->Flow();
	}

	return flow;
}
#pragma once
#ifndef PREFLOWPUSH_HPP
#define PREFLOWPUSH_HPP

#include "MaxFlowAlgorithm.hpp"
#include <cmath>


template<typename T>
class PreflowPush : public MaxFlowAlgorithm<T>
{
	using Iterator = typename Network<T>::Iterator;

	std::vector<T> overflows_;
	std::vector<std::size_t> heights_;
	std::vector<Iterator> iterators_;
	std::size_t overflownCount_;

	bool fromSourceOrTarget(Iterator edge);
	bool toSourceOrTarget(Iterator edge);
	void discharge(std::size_t vertice);

	void fixupOverflows(Iterator edge, T pushed);

	bool canPush(Iterator edge);

	void push(Iterator edge);
	void relabel(std::size_t vertice);

public:
	void Initialize(std::shared_ptr<Network<T>> network) override;

	void Calculate() override;
};

#include "PreflowPush.tpp"

#endif // PREFLOWPUSH_HPP
#include "PreflowPush.hpp"

template<typename T>
void PreflowPush<T>::Initialize(std::shared_ptr<Network<T>> network)
{
	overflows_.assign(network->VerticeCount(), 0);
	heights_.assign(network->VerticeCount(), 0);
	overflownCount_ = 0;

	MaxFlowAlgorithm<T>::Initialize(network);

	iterators_.reserve(network->VerticeCount());
	for (std::size_t i = 0; i < network->VerticeCount(); ++i)
	{
		iterators_.push_back(network->IterateOutgoingEdgesAt(i));
	}
}

template<typename T>
bool PreflowPush<T>::fromSourceOrTarget(Iterator edge)
{
	return edge->Source() == this->network_->Source()
		|| edge->Source() == this->network_->Target();
}

template<typename T>
bool PreflowPush<T>::toSourceOrTarget(Iterator edge)
{
	return edge->Target() == this->network_->Source()
		|| edge->Target() == this->network_->Target();
}

template<typename T>
void PreflowPush<T>::discharge(std::size_t vertice)
{
	while (overflows_[vertice] > 0)
	{
		if (iterators_[vertice])
		{
			push(iterators_[vertice]);
			++iterators_[vertice];
		}
		else
		{
			relabel(vertice);
			iterators_[vertice] = this->network_->IterateOutgoingEdgesAt(vertice);	
		}
	}
}

template<typename T>
bool PreflowPush<T>::canPush(Iterator edge)
{
	return heights_[edge->Source()] == heights_[edge->Target()] + 1
		&& edge->Flow() < edge->Capacity()
		&& (overflows_[edge->Source()] > 0
			|| edge->Source() == this->network_->Source());
}

template<typename T>
void PreflowPush<T>::fixupOverflows(Iterator edge, T pushed)
{
	if (!fromSourceOrTarget(edge))
	{
		if (overflows_[edge->Source()] == pushed)
			--overflownCount_;
		overflows_[edge->Source()] -= pushed;
	}

	if (!toSourceOrTarget(edge))
	{
		if (overflows_[edge->Target()] == 0)
			++overflownCount_;
		overflows_[edge->Target()] += pushed;
	}
}

template<typename T>
void PreflowPush<T>::push(Iterator edge)
{
	if (!canPush(edge))
		return;

	T pushable = std::min(edge->Capacity() - edge->Flow(), overflows_[edge->Source()]);

	if (edge->Source() == this->network_->Source())
			pushable = edge->Capacity() - edge->Flow();

	
	edge->AddFlow(pushable);
	fixupOverflows(edge, pushable);
}

template<typename T>
void PreflowPush<T>::relabel(std::size_t vertice)
{
	std::size_t m = this->network_->VerticeCount();
	for (auto it = this->network_->IterateOutgoingEdgesAt(vertice); it; ++it)
	{
		if (it->Flow() >= it->Capacity())
			continue;

		if (canPush(it))
			return;

		m = std::min(m, heights_[it->Target()]);
	}

	heights_[vertice] = m + 1;
}


template<typename T>
void PreflowPush<T>::Calculate()
{
	Network<T>& network = *this->network_;

	heights_[network.Source()] = 1;
	for (auto it = network.IterateOutgoingEdgesAt(network.Source()); it; ++it)
	{
		push(it);
	}
	heights_[network.Source()] = network.VerticeCount();

	while (overflownCount_ > 0)
	{
		for (std::size_t i = 0; i < network.VerticeCount(); ++i)
		{
			discharge(i);	
		}
	}
}
#include "EdgeListNetwork.hpp"
#include "NetworkBuilder.hpp"
#include "PreflowPush.hpp"


using Type = long long;



int main()
{
	std::size_t vertCount = 0;
	std::cin >> vertCount;

	std::size_t source = 0;
	std::size_t target = 0;
	std::size_t edgeCount = 0;
	std::cin >> source >> target >> edgeCount;

	NetworkBuilder<EdgeListNetwork, Type> builder;
	builder.Initialize(vertCount).SetSource(source).SetTarget(target);

	for (std::size_t i = 0; i < edgeCount; ++i)
	{
		std::size_t from = 0;
		std::size_t to = 0;
		Type cap = 0;
		std::cin >> from >> to >> cap;
		builder.AddCapacity(from - 1, to - 1, cap);
	}

	std::shared_ptr<Network<Type>> network(builder.Finalize());

	PreflowPush<Type> algorithm;
	algorithm.Initialize(network);
	algorithm.Calculate();
	Type answer = algorithm.GetFlow();

	std::cout << answer << std::endl;

	return 0;
}


Compiler output:
a.cc:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
a.cc:86:10: fatal error: Network.tpp: No such file or directory
   86 | #include "Network.tpp"
      |          ^~~~~~~~~~~~~
compilation terminated.