Cod sursa(job #3188780)

Utilizator GhiuzanuEdward Ghiuzan Ghiuzanu Data 3 ianuarie 2024 20:09:21
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

const int MAX_NODES = 100;
vector<int> adjacencyList[1 + 2 * MAX_NODES + 1];
bool pathFound;
queue<int> bfsQueue;
int parent[1 + 2 * MAX_NODES + 1];
int capacityMatrix[1 + 2 * MAX_NODES + 1][1 + 2 * MAX_NODES + 1];

// Function for Breadth-First Search to find augmenting paths
void bfs(int numNodes) {
    pathFound = false;
    for (int i = 0; i <= 2 * numNodes + 1; ++i)
        parent[i] = -1;
    parent[0] = 0;
    bfsQueue.emplace(0);
    while (!bfsQueue.empty()) {
        int node = bfsQueue.front();
        bfsQueue.pop();
        for (int i = 0; i < adjacencyList[node].size(); ++i) {
            int neighbor = adjacencyList[node][i];
            if (parent[neighbor] == -1 && capacityMatrix[node][neighbor] > 0) {
                if (neighbor != 2 * numNodes + 1) {
                    parent[neighbor] = node;
                    bfsQueue.emplace(neighbor);
                } else {
                    pathFound = true;
                }
            }
        }
    }
}

int main(){
    int numNodes;
    fin >> numNodes;

    // Reading capacities from input file
    for (int i = 1; i <= numNodes; ++i)
        fin >> capacityMatrix[0][i] >> capacityMatrix[numNodes + i][2 * numNodes + 1];

    // Setting capacities within the graph
    for (int i = 1; i <= numNodes; ++i)
        for (int j = numNodes + 1; j <= 2 * numNodes; ++j)
            if (numNodes + i != j)
                capacityMatrix[i][j] = 1;

    // Creating the adjacency list representation of the graph
    for (int i = 1; i <= numNodes; ++i) {
        adjacencyList[0].emplace_back(i);
        adjacencyList[i].emplace_back(0);
    }
    for (int i = numNodes + 1; i <= 2 * numNodes; ++i) {
        adjacencyList[i].emplace_back(2 * numNodes + 1);
        adjacencyList[2 * numNodes + 1].emplace_back(i);
    }
    for (int i = 1; i <= numNodes; ++i) {
        for (int j = numNodes + 1; j <= 2 * numNodes; ++j) {
            if (numNodes + i != j) {
                adjacencyList[i].emplace_back(j);
                adjacencyList[j].emplace_back(i);
            }
        }
    }
    int maxFlow = 0;

    // Finding maximum flow in the graph
    while (true) {
        bfs(numNodes);
        if (!pathFound)
            break;
        for (int i = 0; i < adjacencyList[2 * numNodes + 1].size(); ++i) {
            int neighbor = adjacencyList[2 * numNodes + 1][i];
            int minCapacity = 1e9;
            parent[2 * numNodes + 1] = neighbor;
            for (int currentNode = 2 * numNodes + 1; parent[currentNode] != currentNode; currentNode = parent[currentNode])
                minCapacity = min(minCapacity, capacityMatrix[parent[currentNode]][currentNode]);
            for (int currentNode = 2 * numNodes + 1; parent[currentNode] != currentNode; currentNode = parent[currentNode]) {
                capacityMatrix[parent[currentNode]][currentNode] -= minCapacity;
                capacityMatrix[currentNode][parent[currentNode]] += minCapacity;
            }
            maxFlow += minCapacity;
        }
    }

    // Writing maximum flow to output file
    fout << maxFlow << '\n';

    // Writing edges carrying maximum flow to output file
    for (int i = 1; i <= numNodes; ++i)
        for (int j = numNodes + 1; j <= 2 * numNodes; ++j)
            if (numNodes + i != j && capacityMatrix[i][j] == 0)
                fout << i << ' ' << j - numNodes << '\n';

    return 0;
}