Cod sursa(job #2960058)

Utilizator 0SiSBesliu Radu-Stefan 0SiS Data 3 ianuarie 2023 15:11:06
Problema Taramul Nicaieri Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.43 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Declare input and output files
ifstream f("harta.in");
ofstream g("harta.out");

// Declare variables
int n, s, t;
vector < vector < int >> capacity;
list < int > *adjList; // Pointer to an array of linked lists to store adjacency lists
vector < int > parent; // Vector to store the BFS tree

// Function to perform BFS on the residual graph
bool bfs() {
    // Assign all values in the parent vector to 0
    parent.assign(t + 1, 0);
    // Declare a queue to store nodes during BFS
    queue < int > q;

    // Push the source node onto the queue
    q.push(s);

    // While the queue is not empty
    while (!q.empty()) {
        // Get the first element in the queue
        int firstInQueue = q.front();
        q.pop();

        // If the first element in the queue is the sink node, return true
        if (firstInQueue == t) {
            return true;
        }

        // For each adjacent node to the current node
        for (auto const& adjNode: adjList[firstInQueue]) {
            // Get the capacity of the edge between the current node and the adjacent node
            int currentCapacity = capacity[firstInQueue][adjNode];

            // If the capacity is greater than 0 and the parent of the adjacent node has not been set
            if (currentCapacity > 0 && parent[adjNode] == 0) {
                // Set the parent of the adjacent node to the current node
                parent[adjNode] = firstInQueue;
                // Push the adjacent node onto the queue
                q.push(adjNode);
            }
        }
    }

    // Return false if we reach this point, as the sink node has not been found
    return false;
}

// Function to compute the maximum flow using Edmonds-Karp algorithm
int edmondsKarp() {
    // Initialize the maximum flow to 0
    int maxFlow = 0;

    // While there is a path from the source to the sink in the residual graph
    while (bfs()) {
        // For each node in the adjacency list of the sink node
        for (auto const& node: adjList[t]) {
            // If the parent of the node has been set
            if (parent[node]) {
                // Set the parent of the sink node to the current node
                parent[t] = node;

                // Initialize the current flow to the maximum possible value
                int currentFlow = INT_MAX;

                // For each node in the path from the sink to the source
                for (int i = t; i != s; i = parent[i]) {
                    // Find the minimum capacity of the edges in the path
                    currentFlow = min(currentFlow, capacity[parent[i]][i]);
                }

                // For each node in the path from the sink to the source
                for (int i = t; i != s; i = parent[i]) {
                    capacity[parent[i]][i] -= currentFlow;
                    capacity[i][parent[i]] += currentFlow;
                }

                // Add the current flow to the maximum flow
                maxFlow += currentFlow;
            }
        }
    }

    // Return the maximum flow
    return maxFlow;
}

int main() {
    f >> n;
    t = 2 * n + 1;
    adjList = new list < int > [t + 1];
    parent.resize(t + 1);
    capacity.resize(t + 1, vector < int > (t + 1));

    for (int i = 1; i <= n; ++i) {
        int x, y;
        f >> x >> y;
        adjList[s].push_back(i); // Add an edge from the source to the node with capacity x
        adjList[i].push_back(s); // Add an edge from the node to the source with capacity 0
        capacity[s][i] = x; // Set the capacity of the edge from the source to the node to x

        adjList[i + n].push_back(t); // Add an edge from the node to the sink with capacity y
        adjList[t].push_back(i + n); // Add an edge from the sink to the node with capacity 0
        capacity[i + n][t] = y; // Set the capacity of the edge from the node to the sink to y
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j) {
                adjList[i].push_back(j + n);
                adjList[j + n].push_back(i);
                capacity[i][j + n] = 1;
            }
        }
    }

    g << edmondsKarp() << '\n';
    for (int i = 1; i <= n; ++i) {
        for (auto const& node: adjList[i]) {
            if (node != s && node != t && capacity[i][node] == 0) {
                g << i << " " << node - n << '\n';
            }
        }
    }
}