Cod sursa(job #2959463)

Utilizator VladWero08Olaeriu Vlad Mihai VladWero08 Data 31 decembrie 2022 12:24:40
Problema Taramul Nicaieri Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.58 kb
#include <bits/stdc++.h>

using namespace std;

int Nodes;
vector<int> *AdjacencyList, *AdjacencyInnerList;

// Cost matrix, flux matrix
long **flux, **cost;

bool FindUnsaturatedPath(int Source, int Destination, int Nodess, vector<int> *AdList, vector <int> *AdInList, long **flux, long **cost, int *dad, int *visited){
    queue <int> Q;
    int Node;

    for(int i = 0; i <= Nodess; i++){
        visited[i] = dad[i] = 0;
    }

    // Add the source in the queue
    Q.push(Source);
    // Mark the starting node as visited
    visited[Source] = 1;
    while(!Q.empty()){
        Node = Q.front();
        Q.pop();

        // For the edges leaving from Node,
        // check if it can be added more flux
        for(auto NodeNext : AdList[Node]){
            if( visited[NodeNext] != 1 && flux[Node][NodeNext] < cost[Node][NodeNext]){
                dad[NodeNext] = Node;

                // Check if the path reached the destination, and if it did
                // exit the function
                if(NodeNext == Destination)
                    return true;

                Q.push(NodeNext);
                visited[NodeNext] = 1;
            }
        }

        // For the edges coming into Node,
        // check if it can be added more flux
        for(auto NodeNext: AdInList[Node]){
            if( visited[NodeNext] != 1 && flux[Node][NodeNext] > 0){
                dad[NodeNext] = -Node;

                // Check if the path reached the destination, and if it did
                // exit the function
                if(NodeNext == Destination)
                    return true;

                Q.push(NodeNext);
                visited[NodeNext] = 1;
            }
        }
    }
    return false;
}

int main() {
    ////////////////////////////
    /////// READING DATA ///////
    ////////////////////////////
    int AllNodes, InDegree, OutDegree;

    ifstream fin("harta.in");
    fin >> AllNodes;
    // Edmonds Karp Maximum Flow Adaptation
    // We will have a bipartition:
    // --> left set == right set, but there wont be edges
    // from the same node to the same node
    // Also, there will be 2 pseudo nodes:
    // --> source: will have edge to every node, with the capacity of outer degree of that node
    // --> destination: every node will have an edge that ends in 'destination' node with the value of their outer degree
    Nodes = AllNodes * 2 + 2;

    // Resize adjacency lists
    AdjacencyList = new vector<int>[Nodes + 1];
    AdjacencyInnerList = new vector<int>[Nodes + 1];

    // Resize matrixs
    flux = new long* [Nodes + 1];
    cost = new long* [Nodes + 1];

    int source = Nodes - 1, destination = Nodes, dest, maxflow = 0;
    int *dad = new int[Nodes + 1], *visited = new int [Nodes + 1];

    for(int i = 0; i <= Nodes; i++){
        flux[i] = new long [Nodes + 1];
        cost[i] = new long [Nodes + 1];
    }

    for(int i = 1; i <= AllNodes; i++){
        fin >> OutDegree >> InDegree;

        // Update the edge from source => NODEi
        ///////////////////////////////////////
        AdjacencyList[source].push_back(i);
        AdjacencyInnerList[i].push_back(source);

        // Initialize matrixs
        cost[source][i] = OutDegree;
        flux[source][i] = 0;

        // Update the edge from NODEi => destination
        ////////////////////////////////////////////
        AdjacencyList[i + AllNodes].push_back(destination);
        AdjacencyInnerList[destination].push_back(i + AllNodes);

        // Initialize matrixs
        cost[i + AllNodes][destination] = InDegree;
        flux[i + AllNodes][destination] = 0;
    }

    fin.close();

    // We add the maximul flow 1
    // to the rest of the edge
    for(int i = 1; i <= AllNodes; i++){
        for(int j = 1; j <= AllNodes; j++){
            if( i != j){
                AdjacencyList[i].push_back(AllNodes + j);
                AdjacencyInnerList[AllNodes + j].push_back(i);

                // Initialize matrixs
                cost[i][AllNodes + j] = 1;
                flux[i][AllNodes + j] = 0;
            }
        }
    }

    // While we can discover unsaturated path
    while(FindUnsaturatedPath(source, destination, Nodes, AdjacencyList, AdjacencyInnerList, flux, cost, dad, visited)){
        // Calculate the minimum rezidual capacity in the path that the
        // function has found
        long MRC = LONG_MAX;
        dest = destination;

        while(dest != source){
            // Edge leaving from dad
            if(dad[dest] >= 0){
                if( cost[dad[dest]][dest] - flux[dad[dest]][dest] < MRC)
                    MRC = cost[dad[dest]][dest] - flux[dad[dest]][dest];
                dest = dad[dest];
            } else{
                // Edge coming into dad
                if( flux[dest][-dad[dest]] < MRC)
                    MRC = flux[dest][-dad[dest]];
                dest = -dad[dest];
            }
        }
        dest = destination;
        while(dest != source){
            if(dad[dest] > 0){
                flux[dad[dest]][dest] += MRC;
                dest = dad[dest];
            } else{
                flux[dest][-dad[dest]] -= MRC;
                dest = -dad[dest];
            }
        }
        maxflow += MRC;
    }

    ofstream fout("harta.out");
    fout << maxflow << endl;
    for(int i = 1; i <= AllNodes; i++){
        for(int j = 1; j <= AllNodes; j++)
            if(flux[i][j + AllNodes] == 1 && i != j){
                fout << i << " " << j << endl;
            }
    }
    fout.close();
    return 0;
}