#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
// Auxiliary struct for holding edge information
struct Edge {
int source, destination, cost;
Edge(int source, int dest, int cost = 0): source(source), destination(dest), cost(cost){}
// Returns edge with source and destination swapped
Edge Flip() {return Edge(destination, source, cost);}
};
class FlowHandler;
class Graph {
public:
// Holds the max value for int, used to represent infinite distances(for unreachable nodes)
// = 2147483647
static const int INFINITE;
// Returns the sum of all edge weights
int TotalCost();
// Returns the number of connected components (for undirected graphs)
int NumberOfComponents();
// Returns the diameter of the graph(length of longest sequence of connected nodes). Should only be used on trees
int TreeDiameter();
// Returns the maximum flow from source to sink. Should only be used after BuildFlowNetwork() has been called
// Requires handler to be the FlowHandler that was passed to BuildFlowNetwork()
long long MaximumFlow(unsigned int source, unsigned int sink, FlowHandler& handler);
// Returns all edges in the graph
vector<Edge> GetAllEdges();
// Returns a vector of distances from node of index startIndex to all others, ignoring weights
vector<int> UnweightedDistances(int startIndex = 0);
// Returns a vector of distances from node of index startIndex to all others
// Uses Dijkstra's algorithm if there are no negative edges, otherwise uses the Bellman-Ford algorithm
vector<int> WeightedDistances(int startIndex = 0);
// Returns an adjacency matrix, returnMatrix[i][j] represents the cost of the minimum path from node i to node j
// returnMatrix[i][j] == Graph::INFINITE means there is no edge from i to j
vector<vector <int>> AllMinimumDistances();
// Returns a vector containing the topological sort of current graph (for directed graphs)
vector<int> TopologicalSort();
// Returns vectors of node indexes, grouped into the graph's strongly connected components (for directed graphs)
vector<vector <int>> StronglyConnectedComponents();
// Returns vectors of node indexes, grouped into the graph's biconnected components
vector<vector <int>> BiconnectedComponents();
// Returns a vector of the critical edges in the graph
vector<Edge> CriticalConnections();
// Returns a new graph that is the MST of this graph
Graph MinimumSpanningTree();
// Returns a new graph that is the DF search tree of this graph starting in startIndex
Graph DFSTree(int startIndex);
// Returns a new graph that is the BF search tree of this graph starting in startIndex
Graph BFSTree(int startIndex);
// Returns a new graph that contains all DFS trees of this graph
// Starts a DFS from index 0, then visits all unvisited nodes, adding the other trees to the returned graph
Graph DFSTrees();
// Reads edges from inputStream, formated as adjacency list entries: nodeX, nodeY, capacity, cost
// and builds a flow network graph using handler as a helper for operations on the network
// Should only be used after setting numberOfNodes and numberOfEdges
void BuildFlowNetwork(istream& inputStream, FlowHandler& handler);
// Reads edges from inputStream, formated as adjacency list entries: nodeX, nodeY, cost
// Should only be used if numberOfEdges has already been set
void BuildFromAdjacencyList(istream& inputStream);
// Reads edges from inputStream, formated as an adjacency matrix:
// 0 represents no edge, any other value represents the cost of the edge
// If upon calling numberOfEdges == 0 (has not been set), sets numberOfEdges according to the matrix
void BuildFromAdjacencyMatrix(istream& inputStream);
// Returns an adjacency matrix for the graph, returnMatrix[i][j] represents the cost from node i to node j
// returnMatrix[i][j] == Graph::INFINITE means there is no edge from i to j
vector<vector<int>> GetAdjacencyMatrix();
// Adds a new edge to the graph, increases numberOfEdges
void AddEdge(int source, int dest, int cost = 0);
// Adds a new edge to the graph, increases numberOfEdges
void AddEdge(Edge newEdge);
// Adds a new node to the graph, increases numberOfNodes
void AddNode(int value = 0);
// Takes a vector of node degree values and checks if a graph can be formed using the Havel-Hakimi algorithm
static bool CheckHavelHakimi(vector<int> degrees);
#pragma region GraphConstructors
Graph(bool directed = false, bool weighted = false) {
numberOfNodes = 0;
numberOfEdges = 0;
this->directed = directed;
this->weighted = weighted;
}
Graph(int numberOfNodes, int numberOfEdges = 0, bool directed = false, bool weighted = false) {
this->numberOfEdges = numberOfEdges;
this->directed = directed;
this->weighted = weighted;
for(int i = 0; i < numberOfNodes; ++i) {
AddNode();
}
}
#pragma endregion
#pragma region GraphGetSet
void SetValue(int node, int value) {
try {
values[node] = value;
}
catch(...) {
throw "Node doesn't exist";
}
}
int GetValue(int node) const {
try {
return values[node];
}
catch(...) {
throw "Node doesn't exist";
}
}
void SetDirected(bool directed) {
this->directed = directed;
}
bool IsDirected() const {
return directed;
}
void SetWeighted(bool weighted) {
this->weighted = weighted;
}
bool IsWeighted() const {
return weighted;
}
void SetNumberOfNodes(int number) {
numberOfNodes = number;
}
int GetNumberOfNodes() const {
return numberOfNodes;
}
void SetNumberOfEdges(int number) {
numberOfEdges = number;
}
int GetNumberOfEdges() const {
return numberOfEdges;
}
#pragma endregion
private:
bool directed;
bool weighted;
int numberOfNodes;
int numberOfEdges;
vector < int > values; // The value of each node
vector < vector < Edge > > adjacencyList; // adjacencyList[X] holds the information of each edge that X has
void BFS(vector<bool>& visitedNodes, vector<int>& distances, int startIndex = 0);
void FlowBFS(vector<bool>& visitedNodes, vector<int>& prev, FlowHandler& fh, int startIndex, int sink);
void TreeBuilderBFS(int startIndex, Graph& treeGraph, vector<bool>& visitedNodes);
void DFS(vector<int>& visitedNodes, int marker = 1, int nodeIndex = 0);
void StronglyConnectedDFS(int currentNode, vector<vector<int>>& scc, vector<int>& order, vector<int>& lowest, stack<int>& nodeStack, vector<bool>& onStack, int& counter);
void BiconnectedDFS(int currentNode, int parent, int currentDepth, vector< vector <int>>& bcc, vector<int>& depth, vector<int>& lowest, stack<int>& nodeStack, vector<bool>& visited);
void CriticalEdgesDFS(int currentNode, int parent, vector <Edge>& cc, vector<int>& depth, vector<int>& lowest, int& counter);
void TopologicalDFS(int currentNode, stack<int>& orderStack, vector<bool>& visitedNodes);
void TreeBuilderDFS(int currentNode, int treeCurrentNode, Graph& treeGraph, vector<bool>& visitedNodes);
bool HasNegativeEdges();
static bool CompareEdges(Edge x, Edge y);
};
const int Graph::INFINITE = 2147483647;
// Class used as a helper for graph class, to be passed as parameter to graph methods that operate on flow networks
// Should be instantianted after initializing graph with numberOfNodes and numberOfEdges
class FlowHandler {
friend class Graph;
public:
// The matrix for storing capacity of each edge. capacityMatrix[x][y] holds the capacity of the edge x -> y
vector< vector< int >> capacityMatrix;
// Must receive a pointer to the graph that represents the flow network and the indexes of the source and sink nodes
FlowHandler(Graph* graphPointer, int sourceIndex, int sinkIndex): graph(graphPointer), source(sourceIndex), sink(sinkIndex) {
numberOfNodes = graph->GetNumberOfNodes();
for(int i = 0; i < numberOfNodes; ++i) {
vector<int> tempVector;
capacityMatrix.push_back(tempVector);
flowMatrix.push_back(tempVector);
for(int j = 0; j < numberOfNodes; ++j) {
capacityMatrix[i].push_back(0);
flowMatrix[i].push_back(0);
}
}
}
int GetSource() {return source;}
int GetSink() {return sink;}
void SetSource(unsigned int source) {
try {
if (source < numberOfNodes) this->source = source;
else throw;
}
catch (...) {
throw "Source index out of range";
}
}
void SetSink(unsigned int sink) {
try {
if (sink < numberOfNodes) this->sink = sink;
else throw;
}
catch (...) {
throw "Sink index out of range";
}
}
private:
// The graph this FlowHandler is corelated to
const Graph* graph;
int numberOfNodes;
int source, sink;
vector< vector< int >> flowMatrix;
};
#pragma region GraphPublicMethods
void Graph::AddEdge(int source, int dest, int cost /*= 0*/) {
Edge newEdge(source, dest, cost);
adjacencyList[source].push_back(newEdge);
if(!this->directed) {
adjacencyList[dest].push_back(newEdge.Flip());
}
++numberOfEdges;
}
void Graph::AddEdge(Edge newEdge) {
adjacencyList[newEdge.source].push_back(newEdge);
if(!this->directed) {
adjacencyList[newEdge.destination].push_back(newEdge.Flip());
}
++numberOfEdges;
}
int Graph::TotalCost() {
// Returns the summed cost of all edges in graph
int totalCost = 0;
vector<Edge> edges = GetAllEdges();
for(auto edge : edges) {
totalCost += edge.cost;
}
return totalCost;
}
int Graph::TreeDiameter() {
vector<int> distances = UnweightedDistances(); // Perform a BFS
int maximum = 0;
int maxIndex;
for(int i = 0; i < numberOfNodes; ++i) {
if (distances[i] > maximum) {
maximum = distances[i];
maxIndex = i;
}
}
distances = UnweightedDistances(maxIndex); // Perform a second BFS from the node that's farthest away
maximum = 0;
for(int i = 0; i < numberOfNodes; ++i) {
if(distances[i] > maximum) {
maximum = distances[i];
}
}
return maximum + 1; // Add 1 to count starting node
}
long long Graph::MaximumFlow(unsigned int source, unsigned int sink, FlowHandler& handler) {
long long totalFlow = 0;
vector<bool> visited; // For marking visited nodes
vector<int> previous; // Used for tracking paths to sink
for(int i = 0; i < numberOfNodes; ++i) { // Initialization
visited.push_back(false);
previous.push_back(0);
}
FlowBFS(visited, previous, handler, source, sink);
while(visited[sink]) {
for(auto edge : adjacencyList[sink]) { // By checking the paths of all nodes that connect to the sink, we can reduce the number of BFS's that must be performed
previous[sink] = edge.destination;
int minimumIncrease = Graph::INFINITE;
int node = sink; // Current node in path
while(node != source) { // Go back through the path to find the minimum possible increase for the flow of the whole path
int prev = previous[node];
int increase = handler.capacityMatrix[prev][node] - handler.flowMatrix[prev][node];
if(minimumIncrease > increase) {
minimumIncrease = increase;
}
node = prev;
}
if(minimumIncrease != 0) { // If an improvement was found
node = sink;
while(node != source) { // Go back through the path to find the minimum possible increase for the flow of the whole path
int prev = previous[node];
handler.flowMatrix[prev][node] += minimumIncrease;
handler.flowMatrix[node][prev] -= minimumIncrease; // Set residual graph edge
node = prev;
}
totalFlow += minimumIncrease;
}
}
for(int i = 0; i < numberOfNodes; ++i) {
visited[i] = false;
}
FlowBFS(visited, previous, handler, source, sink);
}
return totalFlow;
}
void Graph::BuildFlowNetwork(istream& inputStream, FlowHandler& handler) {
int node1, node2, capacity, cost;
for(int i = 0; i < numberOfEdges; ++i) {
inputStream >> node1 >> node2 >> capacity;
--node1; --node2; // deoarece pe infoarena nodurile sunt indexate de la 1
if(weighted) {
inputStream >> cost;
}
else {
cost = 0;
}
Edge newEdge(node1, node2, cost);
adjacencyList[node1].push_back( newEdge );
adjacencyList[node2].push_back( newEdge.Flip() );
handler.capacityMatrix[node1][node2] = capacity;
}
}
#pragma endregion
#pragma region GraphPrivateMethods
void Graph::FlowBFS(vector<bool>& visitedNodes, vector<int>& prev, FlowHandler& fh, int source, int sink) {
// Performs BF searches for Edmonds-Karp algorithm, setting the previous node for each node it reaches
queue<int> nodeQueue;
nodeQueue.push(source);
while(!nodeQueue.empty()) {
int currentNode = nodeQueue.front();
nodeQueue.pop();
visitedNodes[currentNode] = true;
if(currentNode != sink) {
for(auto edge: adjacencyList[currentNode]) {
int neighbor = edge.destination;
if(!visitedNodes[neighbor] && fh.flowMatrix[currentNode][neighbor] < fh.capacityMatrix[currentNode][neighbor]) { // If more flow can fit
prev[neighbor] = currentNode;
nodeQueue.push(neighbor);
}
}
}
}
}
void Graph::DFS(vector<int>& visitedNodes, int marker /*= 1*/, int nodeIndex /*= 0*/) {
// Recursive depth-first search, sets visited positions in visitedNodes with marker for counting components
visitedNodes[nodeIndex] = marker;
for(auto edge : adjacencyList[nodeIndex]) {
int neighbor = edge.destination;
if(!visitedNodes[neighbor]) {
DFS(visitedNodes, marker, neighbor);
}
}
}
void Graph::StronglyConnectedDFS(int currentNode, vector<vector<int>>& scc, vector<int>& order, vector<int>& lowest, stack<int>& nodeStack, vector<bool>& onStack, int& counter) {
order[currentNode] = counter;
lowest[currentNode] = counter;
++counter;
nodeStack.push(currentNode);
onStack[currentNode] = true;
for(auto edge : adjacencyList[currentNode]) {
int neighbor = edge.destination;
if(order[neighbor] < 0) { // If node hasn't been visited yet
StronglyConnectedDFS(neighbor, scc, order, lowest, nodeStack, onStack, counter);
lowest[currentNode] = min(lowest[currentNode], lowest[neighbor]); // Set the SCC index of each node on the recursion return path
}
else {
if (onStack[neighbor]) {
// If neighbor isn't on the stack, then neighbor is part of a different, previously discovered SCC
lowest[currentNode] = min(lowest[currentNode], order[neighbor]);
}
}
}
if(lowest[currentNode] == order[currentNode]) { // If lowest[X] = order[X] then X has no back-edge and is the root of its SCC
// The stack must be popped up to said root, as we have found a complete SCC
vector<int> currentScc;
int stackTop;
do {
stackTop = nodeStack.top();
nodeStack.pop();
onStack[stackTop] = false;
currentScc.push_back(stackTop);
} while (currentNode != stackTop);
scc.push_back(currentScc);
}
}
void Graph::CriticalEdgesDFS(int currentNode, int parent, vector <Edge>& cc, vector<int>& order, vector<int>& lowest, int& counter) {
order[currentNode] = counter;
lowest[currentNode] = counter;
++counter;
for(auto edge : adjacencyList[currentNode]) {
int child = edge.destination;
if(order[child] < 0) {
CriticalEdgesDFS(child, currentNode, cc, order, lowest, counter);
lowest[currentNode] = min(lowest[currentNode], lowest[child]); // Update lowest after subtree is finished
if (lowest[child] > order[currentNode]) {
// We can't reach the current node through any path that doesn't include the current edge
// So current edge is critical
cc.push_back(edge);
}
}
else if (child != parent || directed) { // Found visited node, so a back-edge
// The if condition is necessary so we don't go back through the edge we just used
lowest[currentNode] = min(lowest[currentNode], order[child]);
}
}
}
void Graph::BiconnectedDFS(int currentNode, int parent, int currentDepth, vector< vector <int>>& bcc, vector<int>& depth, vector<int>& lowest, stack<int>& nodeStack, vector<bool>& visited) {
depth[currentNode] = currentDepth;
lowest[currentNode] = currentDepth;
visited[currentNode] = true;
nodeStack.push(currentNode);
for(auto edge : adjacencyList[currentNode]) {
int child = edge.destination;
if (child != parent) { // Check is required to prevent loops
if(visited[child]) {
lowest[currentNode] = min(lowest[currentNode], depth[child]); // Back-edge is found
}
else {
BiconnectedDFS(child, currentNode, currentDepth +1, bcc, depth, lowest, nodeStack, visited);
lowest[currentNode] = min(lowest[currentNode], lowest[child]); // Update with lowest depth descendants can reach
if(depth[currentNode] <= lowest[child]) { // If true, then child can't reach above current depth, so current node separates two BCCs
vector < int > currentBcc;
currentBcc.push_back(currentNode); // Current node is part of both BCCs that it separates
int stackTop;
do {
stackTop = nodeStack.top();
nodeStack.pop();
currentBcc.push_back(stackTop);
} while ( stackTop != child );
bcc.push_back(currentBcc);
}
}
}
}
}
void Graph::TopologicalDFS(int currentNode, stack<int>& orderStack, vector<bool>& visitedNodes) {
visitedNodes[currentNode] = true;
for(auto edge : adjacencyList[currentNode]) {
int node = edge.destination;
if(!visitedNodes[node]) {
TopologicalDFS(node, orderStack, visitedNodes);
}
}
orderStack.push(currentNode); // The stack is formed in the return order of the DFS
}
#pragma endregion
int main() {
// incerc sa trimit cu o dimnesiune mai mica poate merge mai repede
ifstream inputFile("maxflow.in");
ofstream outputFile("maxflow.out");
int numberOfNodes, numberOfEdges;
inputFile >> numberOfNodes >> numberOfEdges;
Graph graph(numberOfNodes, numberOfEdges, true, false);
FlowHandler fh(&graph, 0, numberOfNodes-1);
graph.BuildFlowNetwork(inputFile,fh);
outputFile << graph.MaximumFlow(0, numberOfNodes-1, fh);
return 0;
}