Cod sursa(job #2962371)

Utilizator bbia17Baicoianu Bianca bbia17 Data 8 ianuarie 2023 14:29:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int N, sursa, dest,x,y;

int ad[201][201];
vector<bool> viz;
vector<int> tata;

int BFS()
{
    tata.clear();
    tata.resize(dest + 1, 0);
    viz.clear();
    viz.resize(dest + 1, false);

    tata[sursa] = -1;
    viz[sursa] = true;

    queue<int> q;
    q.push(sursa);

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

        if (nod == dest) return 1;      // nu flux maxim

        for (int i = 1; i <= dest; i++)

            if (!viz[i] && ad[nod][i] > 0)  // cond nod nevizitat si capacitate nedepasita
            {
                tata[i] = nod;

                viz[i] = true;
                q.push(i);
            }
    }
    // daca nu am ajuns in dest→ flux max
    return 0;
}

int FordFulkerson()
{
    long maxFlux = 0;

    while (BFS())	//cat timp flux nu e maxim
    {
        // PENTRU FIECARE NOD, PARCURGEM DRUMUL GASIT
        for (int i = 1; i <= N; i++)
        {
            if (viz[i + N] && ad[i + N][dest] > 0)
            {
                tata[dest] = i + N;

                // determinam val min a gradelor
                int flux = INT_MAX;
                for (int nod = dest; nod != sursa; nod = tata[nod])
                    flux = min(flux, ad[tata[nod]][nod]);

                // actualizam valorile gradelor nodurilor
                for (int nod = dest; nod != sursa; nod = tata[nod])
                {
                    ad[tata[nod]][nod] -= flux;
                    ad[nod][tata[nod]] += flux;
                }

                maxFlux += flux;
            }
        }
    }
    return maxFlux;
}

int main()
{
    fin>>N;
    // adaugam un nod sursa si unul destinatie
    sursa = 0, dest = 2 * N + 1;

    for (int i = 1; i <= N; i++)
    {
        fin>>y>>x; // y = grd_ext, x = grd_int

        ad[sursa][i] = y; // adaugam muchie de la sursa; cost = grd_ext
        ad[i + N][dest] = x; // adaugam muchie la dest; cost = grd_int

        // adaugam muchiile intre noduri, capacitate = 1
        for (int j = 1; j <= N; j++)
            if (i != j) // conditie noduri distincte
                ad[i][j + N] = 1;
    }

    fout<<FordFulkerson()<<'\n';
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (ad[i][j + N] == 0 && i != j)    // cond capacitate si noduri distincte
                fout<<i<<' '<<j<<'\n';
    return 0;
}