Cod sursa(job #2803481)

Utilizator waren4Marius Radu waren4 Data 20 noiembrie 2021 02:36:39
Problema Flux maxim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 21.79 kb
#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;
}