Cod sursa(job #3190332)

Utilizator dandragosDan Dragos dandragos Data 7 ianuarie 2024 15:22:53
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.98 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>

using namespace std;

const int MAX_VERTICES = 500;
const int INFINITY_FLOW = 0xffffff;

int networkCapacity[MAX_VERTICES][MAX_VERTICES];
int networkFlow[MAX_VERTICES][MAX_VERTICES];
vector<int> adjacencyList[MAX_VERTICES];
int parentNode[MAX_VERTICES];
bool isNodeVisited[MAX_VERTICES];
int totalNodes, maximumFlow, minimumCapacity;

int inDegrees[MAX_VERTICES];
int outDegrees[MAX_VERTICES];

queue<int> bfsTraversal;
int DESTINATION_NODE;

ifstream fileInput("map.in");
ofstream fileOutput("map.out");

bool performBFS()
{
    bfsTraversal.push(1);
    memset(isNodeVisited, false, sizeof(isNodeVisited));
    isNodeVisited[1] = true;

    while (!bfsTraversal.empty())
    {
        int current = bfsTraversal.front();
        bfsTraversal.pop();

        if (current == DESTINATION_NODE)
            continue;

        for (int i = 0; i < adjacencyList[current].size(); ++i)
        {
            int neighbor = adjacencyList[current][i];
            if (networkCapacity[current][neighbor] == networkFlow[current][neighbor] || isNodeVisited[neighbor])
                continue;

            isNodeVisited[neighbor] = true;
            bfsTraversal.push(neighbor);
            parentNode[neighbor] = current;
        }
    }
    return isNodeVisited[DESTINATION_NODE];
}

void computeMaxFlow()
{
    fileInput >> totalNodes;
    DESTINATION_NODE = totalNodes * 2 + 2;

    for (int i = 1; i <= totalNodes; ++i)
    {
        fileInput >> outDegrees[i] >> inDegrees[i];
    }

    for (int i = 1; i <= totalNodes; ++i)
    {
        networkCapacity[1][i + 1] = outDegrees[i];
        adjacencyList[1].push_back(i + 1);
        adjacencyList[i + 1].push_back(1);

        networkCapacity[1 + totalNodes + i][DESTINATION_NODE] = inDegrees[i];
        adjacencyList[i + 1 + totalNodes].push_back(DESTINATION_NODE);
        adjacencyList[DESTINATION_NODE].push_back(i + 1 + totalNodes);
    }

    for (int i = 1; i <= totalNodes; ++i)
    {
        for (int j = i + 1; j <= totalNodes; ++j)
        {
            networkCapacity[i + 1][j + totalNodes + 1] = 1;
            adjacencyList[i + 1].push_back(j + totalNodes + 1);
            adjacencyList[j + totalNodes + 1].push_back(i + 1);

            networkCapacity[j + 1][i + totalNodes + 1] = 1;
            adjacencyList[j + 1].push_back(i + totalNodes + 1);
            adjacencyList[i + totalNodes + 1].push_back(j + 1);
        }
    }

    maximumFlow = 0;
    performBFS();

    while (performBFS())
    {
        for (int i = 0; i < adjacencyList[DESTINATION_NODE].size(); ++i)
        {
            int current = adjacencyList[DESTINATION_NODE][i];
            if (networkCapacity[current][DESTINATION_NODE] == networkFlow[current][DESTINATION_NODE] || !isNodeVisited[current])
                continue;

            minimumCapacity = INFINITY_FLOW;
            parentNode[DESTINATION_NODE] = current;
            for (int i = DESTINATION_NODE; i != 1; i = parentNode[i])
                minimumCapacity = min(minimumCapacity, networkCapacity[parentNode[i]][i] - networkFlow[parentNode[i]][i]);

            if (minimumCapacity == 0)
                continue;

            for (int i = DESTINATION_NODE; i != 1; i = parentNode[i])
            {
                networkFlow[parentNode[i]][i] += minimumCapacity;
                networkFlow[i][parentNode[i]] -= minimumCapacity;
            }
            maximumFlow += minimumCapacity;
        }
    }

    vector<pair<int, int>> resultEdges;
    for (int i = 1; i <= totalNodes; ++i)
    {
        for (int j = 1; j <= totalNodes; ++j)
        {
            if (i != j && networkFlow[i + 1][j + totalNodes + 1] == 1)
            {
                resultEdges.push_back({i, j});
            }
        }
    }

    fileOutput << resultEdges.size() << "\n";
    for (auto edge : resultEdges)
    {
        fileOutput << edge.first << " " << edge.second << "\n";
    }
}

int main()
{
    computeMaxFlow();

    fileInput.close();
    fileOutput.close();

    return 0;
}