Cod sursa(job #2959350)

Utilizator asparagusNadu Toma asparagus Data 30 decembrie 2022 19:03:51
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 8.41 kb
#include <bits/stdc++.h>
using namespace std;


// slightly modified BFS - used to find augmenting paths
bool BFS(const vector<pair<int, int>> *forwardAdjacencyList, const vector<pair<int, int>> *backwardAdjacencyList,
         const vector<vector<pair<int, int>>> &capacityAndFlow, int *parentOf, int numberOfNodes, int sourceNode,
         int sinkNode) {
    // declaring and initializing 'isVisited' array
    bool isVisited[numberOfNodes];
    for (int i = 0; i < numberOfNodes; i++)
        isVisited[i] = false;

    queue<int> workingQueue;
    // BFS begins from the source node
    workingQueue.push(sourceNode);
    isVisited[sourceNode] = true;


    // BFS stalls when no more nodes can be
    // accessed or when the sink node is reached
    while (not workingQueue.empty()) {
        int currentNode = workingQueue.front();
        workingQueue.pop();

        // traversing adjacent nodes reachable from forward edges
        for (auto adjacentNode: forwardAdjacencyList[currentNode])
            // only edges with non-null residual edges can be traversed
            if (capacityAndFlow[currentNode][adjacentNode.first].first -
                capacityAndFlow[currentNode][adjacentNode.first].second > 0) {
                // sink node reached
                if (adjacentNode.first == sinkNode) {
                    // marking the parent of the sink node accordingly
                    parentOf[sinkNode] = currentNode;
                    return true;
                }
                    // unvisited node reached
                else if (not isVisited[adjacentNode.first]) {
                    // pushed to the queue
                    workingQueue.push(adjacentNode.first);
                    // setting the parent node
                    parentOf[adjacentNode.first] = currentNode;
                    // marked as visited
                    isVisited[adjacentNode.first] = true;
                }
            }

        // traversing adjacent nodes reachable from backward edges;
        // the same exact operations occur
        for (auto adjacentNode: backwardAdjacencyList[currentNode])
            if (capacityAndFlow[currentNode][adjacentNode.first].first -
                capacityAndFlow[currentNode][adjacentNode.first].second > 0) {
                if (adjacentNode.first == sinkNode) {
                    parentOf[sinkNode] = currentNode;
                    return true;
                } else if (not isVisited[adjacentNode.first]) {
                    workingQueue.push(adjacentNode.first);
                    parentOf[adjacentNode.first] = currentNode;
                    isVisited[adjacentNode.first] = true;
                }
            }
    }

    // sink node could not be reached -> augmenting path couldn't be found
    return false;
}



// driver function, based on the Edmonds-Karp algorithm
bool generateDirectedGraphEdmondsKarp(const vector<pair<int, int>> *forwardAdjacencyList, int numberOfNodes, int numberOfEdgesToBeConstructed, int sourceNode, int sinkNode) {
    // matrix which holds both the capacity and the currently running flow of an edge from node i to node j
    vector<vector<pair<int, int>>> capacityAndFlow(numberOfNodes,
                                                   vector<pair<int, int>>(numberOfNodes, pair<int, int>()));
    // since there can be a bidirectional edge between two nodes in the original graph, it's easiest
    // to maintain a separate adjacency list for backwards edges, not to overwrite the original
    // bidirectional edges with backward edges, if there are any;
    vector<pair<int, int>> backwardAdjacencyList[numberOfNodes];

    // initializing the backward adjacency list and the capacity-flow matrix
    for (int node = 0; node < numberOfNodes; node++)
        for (auto adjacentNode: forwardAdjacencyList[node]) {
            // storing backward edge
            backwardAdjacencyList[adjacentNode.first].emplace_back(node, adjacentNode.second);

            // all pairs in the matrix are initially 0;
            // even though the forward and backwards edges are stored in distinct
            // adjacency lists, both the capacity and flow will be shared between
            // edges with the same direction, but different types (one forward, one
            // backward), since it is the same as keeping them separate;
            // in order to achieve this, their capacities and flows will be summed
            // up from the very beginning;
            // from now on, whether a forward or backward edge with the same direction
            // connecting the same two nodes will be chosen is indifferent;

            // adding the capacity of the forward edge
            capacityAndFlow[node][adjacentNode.first].first += adjacentNode.second;
            // the flow of the forward edge is initially 0, therefore it was omitted

            // adding the capacity of the backward edge
            capacityAndFlow[adjacentNode.first][node].first += adjacentNode.second;
            // adding the flow of the backward edge;
            // since the residual capacity is the total capacity - the current flow,
            // the backward edge is essentially saturated, so it can't be traversed
            // anymore;
            capacityAndFlow[adjacentNode.first][node].second += adjacentNode.second;
        }


    int parentOf[numberOfNodes], maxFlow = 0;
    // algorithm stalls when no more augmenting paths exist
    while (BFS(forwardAdjacencyList, backwardAdjacencyList, capacityAndFlow, parentOf, numberOfNodes, sourceNode, sinkNode)) {
        // initializing current flow through the found path
        int currentFlowUnits = INT_MAX;

        // first path reconstruction based on 'parentOf' array;
        // computing the minimum flow units which can be pushed
        // through the augmenting path
        for (int childNode = sinkNode; childNode != sourceNode; childNode = parentOf[childNode]) {
            int parentNode = parentOf[childNode];

            // residual capacity = total capacity - current flow
            if (capacityAndFlow[parentNode][childNode].first - capacityAndFlow[parentNode][childNode].second <
                currentFlowUnits)
                currentFlowUnits = capacityAndFlow[parentNode][childNode].first - capacityAndFlow[parentNode][childNode].second;
        }

        // second path reconstruction -> updating the flow of every edge of the augmenting path
        for (int childNode = sinkNode; childNode != sourceNode; childNode = parentOf[childNode]) {
            int parentNode = parentOf[childNode];

            // residual capacity of forward edge + residual capacity of backward edge = total capacity;
            // whenever the flow of one of the edges is modified, the other must be updated accordingly;
            // adding flow units to the chosen edge
            capacityAndFlow[parentNode][childNode].second += currentFlowUnits;
            // removing the same amount of flow units from the opposite edge
            capacityAndFlow[childNode][parentNode].second -= currentFlowUnits;
        }

        maxFlow += currentFlowUnits;
    }

    cout<<maxFlow;

    if (maxFlow!=numberOfEdgesToBeConstructed)
        return false;
    
    ofstream output("harta.out");

    output << maxFlow <<'\n';

    for (int outNode = 1; outNode <= numberOfNodes/2 - 1; outNode++)
        for (auto inNode : forwardAdjacencyList[outNode])
            if (capacityAndFlow[outNode][inNode.first].second == 1)
                output<<outNode<<' '<<inNode.first - (numberOfNodes/2 - 1)<<'\n';

    output.close();
    
    return true;
}



int main() {
    ifstream input("harta.in");

    int numberOfNodes;
    input >> numberOfNodes;

    vector<pair<int, int>> adjacencyList[numberOfNodes*2+2];

    int outDegree, inDegree, numberOfEdgesToBeConstructed=0;
    for (int node = 1; node <= numberOfNodes; node++) {
        input >> outDegree >> inDegree;
        numberOfEdgesToBeConstructed += inDegree;
        
        adjacencyList[0].emplace_back(node, outDegree);

        for (int adjacentNode = 1; adjacentNode <= numberOfNodes; adjacentNode++)
            if (adjacentNode!=node)
                adjacencyList[node].emplace_back(adjacentNode+numberOfNodes, 1);

        adjacencyList[node+numberOfNodes].emplace_back(numberOfNodes*2+1, inDegree);
    }

    input.close();

    if (not generateDirectedGraphEdmondsKarp(adjacencyList, numberOfNodes*2+2, numberOfEdgesToBeConstructed, 0, numberOfNodes*2 + 1)) {
        ofstream output("harta.out");
        output<<"None";
        output.close();
    }

    return 0;
}