Cod sursa(job #3190330)

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

using namespace std;

const int MAX_NODES = 505;
const int INFINITY_VAL = 0xfffff;

int capacities[MAX_NODES][MAX_NODES];
int flows[MAX_NODES][MAX_NODES];
vector<int> adjacency[MAX_NODES];
int parents[MAX_NODES];
bool visitedNodes[MAX_NODES];
int totalNodes, maxFlowValue, minCapacityValue;

int inDegrees[MAX_NODES];
int outDegrees[MAX_NODES];

queue<int> bfsQueue;
int DEST_NODE;

ifstream inputFile("input_file.in");
ofstream outputFile("output_file.out");

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

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

        if (current == DEST_NODE)
            continue;

        for (int i = 0; i < adjacency[current].size(); ++i)
        {
            int neighbor = adjacency[current][i];
            if (capacities[current][neighbor] == flows[current][neighbor] || visitedNodes[neighbor])
                continue;

            visitedNodes[neighbor] = true;
            bfsQueue.push(neighbor);
            parents[neighbor] = current;
        }
    }
    return visitedNodes[DEST_NODE];
}

void solveNetworkFlow()
{
    inputFile >> totalNodes;
    DEST_NODE = totalNodes * 2 + 2;

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

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

        capacities[1 + totalNodes + i][DEST_NODE] = inDegrees[i];
        adjacency[i + 1 + totalNodes].push_back(DEST_NODE);
        adjacency[DEST_NODE].push_back(i + 1 + totalNodes);
    }

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

            capacities[j + 1][i + totalNodes + 1] = 1;
            adjacency[j + 1].push_back(i + totalNodes + 1);
            adjacency[i + totalNodes + 1].push_back(j + 1);
        }
    }

    maxFlowValue = 0;
    performBFS();

    while (performBFS())
    {
        for (int i = 0; i < adjacency[DEST_NODE].size(); ++i)
        {
            int current = adjacency[DEST_NODE][i];
            if (capacities[current][DEST_NODE] == flows[current][DEST_NODE] || !visitedNodes[current])
                continue;

            minCapacityValue = INFINITY_VAL;
            parents[DEST_NODE] = current;
            for (int i = DEST_NODE; i != 1; i = parents[i])
                minCapacityValue = min(minCapacityValue, capacities[parents[i]][i] - flows[parents[i]][i]);

            if (minCapacityValue == 0)
                continue;

            for (int i = DEST_NODE; i != 1; i = parents[i])
            {
                flows[parents[i]][i] += minCapacityValue;
                flows[i][parents[i]] -= minCapacityValue;
            }
            maxFlowValue += minCapacityValue;
        }
    }

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

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

int main()
{
    solve();

    inputFile.close();
    outputFile.close();

    return 0;
}