Cod sursa(job #3190205)

Utilizator CosteaCristian1Costea Cristian-Nicolaie CosteaCristian1 Data 7 ianuarie 2024 11:13:44
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <fstream>

using namespace std;

#define NMAX 256
vector<int> Graph[NMAX];

int NumCities, DestinationNode;
int Capacities[NMAX][NMAX];
int Previous[NMAX + 4];

// Algoritmul Bellman-Ford pentru gasirea drumurilor de crestere
bool BellmanFord()
{
    vector<int>::iterator it;
    memset(Previous, -1, sizeof(Previous));

    int node;
    queue<int> Queue;
    Queue.push(0);

    while (!Queue.empty())
    {
        node = Queue.front();
        if (node == DestinationNode)
            break;

        // Parcurgere noduri adiacente pentru gasirea drumurilor de crestere
        for (it = Graph[node].begin(); it != Graph[node].end(); ++it)
        {
            if (Previous[*it] == -1 && Capacities[node][*it] > 0)
            {
                Queue.push(*it);
                Previous[*it] = node;
            }
        }
        Queue.pop();
    }
    if (node != DestinationNode)
        return true;

    // Modificarea fluxului pe drumurile de crestere gasite
    for (node = DestinationNode; node; node = Previous[node])
    {
        --Capacities[Previous[node]][node];
        ++Capacities[node][Previous[node]];
    }

    return false;
}
ofstream fout("harta.out");
// Afisarea drumurilor cu capacitati nule
void ShowPaths()
{
    int i, j;
    for (i = 1; i <= NumCities; ++i)
        for (j = 1; j <= NumCities; ++j)
            if (i != j && !Capacities[i][j + NumCities])
            {
                fout << i << " " << j << "\n";
            }
}

// Rezolvarea problemei utilizand algoritmul de flux maxim
void SolveProblem()
{
    int Answer = 0;

    // Gasirea repetata a drumurilor de crestere pana cand nu mai exista
    while (!BellmanFord())
        ++Answer;

    // Afisarea rezultatelor
    fout << Answer << "\n";
    ShowPaths();
}

int main()
{
    ifstream fin("harta.in");

    // Citirea numarului de orase
    fin >> NumCities;
    DestinationNode = (NumCities << 1) + 2;

    int i, j;
    int Outgoing, Incoming;

    // Initializarea grafului si capacitatilor
    for (i = 1; i <= NumCities; ++i)
    {
        fin >> Outgoing >> Incoming;

        Graph[i].push_back(0);
        Graph[0].push_back(i);
        Capacities[0][i] = Outgoing;

        Graph[i + NumCities].push_back(DestinationNode);
        Graph[DestinationNode].push_back(i + NumCities);
        Capacities[i + NumCities][DestinationNode] = Incoming;

        // Adaugarea drumurilor intre orase cu capacitati
        for (j = 1; j <= NumCities; ++j)
        {
            if (j != i)
            {
                Graph[i].push_back(j + NumCities);
                Graph[j + NumCities].push_back(i);
                Capacities[i][j + NumCities] = 1;
                Capacities[j + NumCities][i] = 0;
            }
        }
    }

    SolveProblem();

    fin.close();
    fout.close();

    return 0;
}