Cod sursa(job #2959235)

Utilizator alexdn6Dina Alexandru alexdn6 Data 30 decembrie 2022 11:53:48
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream f ("harta.in");
ofstream g ("harta.out");

vector<vector<int>> grade;
vector<vector<int>> graf(202, vector<int>(202, 0));
vector<int> parinte(202);
vector<bool> vizitat(202);
queue <int> coada;

// Pentru rezolvare vom folosi indicațiile din curs
// Anume, adăugăm un nod de start, un nod de terminal
// Formăm două mulțimi de noduri, prima mulțime o legăm la nodul de start
// A doua de nodul terminal
// Apoi, intre nodurile din cele multimi adaugam muchii, cu exceptia cand au acelasi indice (i == j)
// Adăugăm fluxul
// Apoi folosim aceeași metodă de rezolvarea ca la problema cu fluxul
// Complexitate (conform curs) O(m^2)

int n;
bool bfs(int n)
{
    coada = queue <int> (); // golesc coada
    fill(vizitat.begin(), vizitat.end(), false);
    fill(parinte.begin(), parinte.end(), -1);

    coada.push(0);
    vizitat[0] = true;

    while(!coada.empty())
    {
        int nod = coada.front();
        coada.pop();

        for(int i = 0; i <= n; i++)
        {
            if(graf[nod][i] > 0 && !vizitat[i])
            {
                coada.push(i);
                vizitat[i] = true;
                parinte[i] = nod;
                if(i == n)
                {
                    return true;
                }
            }
        }
    }
    return false;
}
int FluxMaxim(int n)
{
    int fluxMaxim = 0;

    while(bfs(n))
    {
        for(int u = 1; u < n; u++)
        {
            if(graf[u][n] > 0 && vizitat[u])
            {
                vector<int> drum;
                int capacitateMinima = INT_MAX;
                drum.push_back(n);
                drum.push_back(u);

                int tata = parinte[u];

                while(tata != -1)
                {
                    drum.push_back(tata);
                    tata = parinte[tata];
                }

                for(long unsigned int v = 1; v < drum.size(); v++)
                    capacitateMinima = min(capacitateMinima, graf[drum[v]][drum[v - 1]]);

                fluxMaxim = fluxMaxim + capacitateMinima;

                for(long unsigned int v = 1; v < drum.size(); v++) {
                    graf[drum[v]][drum[v - 1]] -= capacitateMinima;
                    graf[drum[v - 1]][drum[v]] += capacitateMinima;
                }
            }
        }
    }

    return fluxMaxim;
}
int main() {

    f >> n;
    grade.resize(n + 1);

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

    f.close();

// Precum în exemplul din curs, adăugăm un nod de start (0), și un
// un nod terminal (2 * n + 1) (2 * n pentru că avem cele două mulțimi)
// fluxul de la nodul de start la noduri va fi cel de pe prima coloană din
// fisierul de intrare, iar cel de la nodurile din a doua multime la terminal
// va fi cel de pe a doua coloana


    for(int i = 1; i <= n; i++) {
        graf[0][i] = grade[i][0];
        graf[i + n][2 * n + 1] = grade[i][1];
    }

// Acum adăugăm fluxul între nodurile din cele 2 multimi
// (conform cursului, acesta va fi 1)

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j)
                graf[i][n + j] = 1; //punem n + j ca sa fie din a doua multime

    g << FluxMaxim(2 * n + 1) << "\n";

    for(int i = 1; i <= n; i++)
        for(int j = n + 1; j <= n * 2; j++)
            if(graf[j][i] != 0)
                g << i << " " << j - n << "\n";
    return 0;
}