Cod sursa(job #3188442)

Utilizator Maria_VerdesVerdes Maria-Ioana Maria_Verdes Data 2 ianuarie 2024 21:53:21
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

int main()
{
    int n;
    f >> n;

    // vrem sa construim o retea corespunzatoare grafului pe care vrem sa-l construim
    // luam un graf bipartit avand in ambele parti cate o copie a nodurile din graful pe care vrem sa-l construim

    // nodul 0 = nodul de start
    // nodul n * 2 + 1 = nodul final
    // de la nodul de start la nodurile noastre vom avem muchii cu capacitatea = gradele de iesire
    // la nodul final de la noduri vom avea muchii cu capacitatea = gradele de intrare

    int last = n * 2 + 1;
    vector <vector <int>> vecini(last + 1, vector <int> ());
    vector <vector <int>> capacitate(last + 1, vector <int> (last + 1, 0));
    vector <vector <int>> flux(last + 1, vector <int>(last + 1, 0));

    for(int i = 1; i <= n; i++)
    {
        int in, out;
        f >> out >> in;

        vecini[0].push_back(i);
        vecini[i].push_back(0);
        capacitate[0][i] = out;

        vecini[last].push_back(n + i);
        vecini[n + i].push_back(last);
        capacitate[i + n][last] = in;
    }
    f.close();

    // construim muchiile intre potentialii vecini de capacitate 1
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j)
            {
                vecini[i].push_back(j + n);
                vecini[j + n].push_back(i);
                capacitate[i][j + n] = 1;
            }


    // determinam fluxul maxim pe reteaua construita
    bool avemDrumDeCrestere = true;
    while(avemDrumDeCrestere)
    {
        avemDrumDeCrestere = false;

        //cautam cu bfs un lant de la nodul de start la cel de finish in care sa putem creste fluxul
        queue <int> q;
        vector <int> tata(last + 1); // daca muchia intoarce flux => -tata
        vector <bool> vis(last + 1, false);

        //initializare vector de tati
        for(int i = 0; i <= last; i++)
            tata[i] = i;

        q.push(0);
        vis[0] = true;
        while(!q.empty())
        {
            int nod = q.front();
            q.pop();
            for(int i = 0; i < vecini[nod].size(); i++)
            {
                int vecin = vecini[nod][i];

                if(capacitate[nod][vecin] > flux[nod][vecin] && !vis[vecin])
                {
                    q.push(vecin);
                    vis[vecin] = true;
                    tata[vecin] = nod;

                    // daca am gasit un lant pana la nodul final
                    if(vecin == last)
                    {
                        avemDrumDeCrestere = true;
                        break;
                    }
                }
            }
        }

        // daca avem drum
        if(avemDrumDeCrestere)
        {
            // il parcurgem si aflam fluxul maxim pe care putem sa-l pusham pe toate muchiile
            int nodCurent = last;
            int fluxMaxim = 100; // fluxul nostru maxim pe un drum oricum e 1
            while(nodCurent != 0)
            {
                int predecesor = tata[nodCurent];
                if(fluxMaxim > capacitate[predecesor][nodCurent] - flux[predecesor][nodCurent])
                    fluxMaxim = capacitate[predecesor][nodCurent] - flux[predecesor][nodCurent];

                nodCurent = predecesor;
            }

            // il parcurgem si pusham fluxul respectiv pe fiecare muchie
            nodCurent = last;
            while(nodCurent != 0)
            {
                int predecesor = tata[nodCurent];

                flux[predecesor][nodCurent] += fluxMaxim;
                flux[nodCurent][predecesor] -= fluxMaxim;

                nodCurent = predecesor;
            }
        }
    }

    // avem muchii = suma gradelor de intrare / iesire

    int m = 0;
    for(int i = 1; i <= n; i++)
        m += capacitate[0][i];
    g << m << endl;

    // parcurgem reteaua si vedem care muchii au fost saturate => nodurile au devenit vecini

    for(int i = 1; i <= n; i++)
        for(int j = 1 + n; j <= n * 2; j++)
            if(flux[i][j])
                g << i << ' ' << j - n << endl;

    g.close();
    return 0;
}