Cod sursa(job #3188195)

Utilizator corinarobuRobu Corina corinarobu Data 2 ianuarie 2024 13:14:19
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;


ifstream f("harta.in");
ofstream g("harta.out");
int nr_noduri, sursa, destinatie, ies , intra, nr_muchii;

//Ford-Fulkerson, bazat pe BFS

int bfs(int sursa, int destinatie, vector<int>& tata, vector<vector<int>>& muchii,
            vector<vector<int>>& capacitate, vector<vector<int>>& flux){

    for(int i = 0; i < tata.size(); i++)
        tata[i] = -1;

    int f_min = INT_MAX;

    tata[sursa] = sursa;
    queue<int> q;
    q.push(sursa);
// verific toate muchile (sursa - noduri coloana 1, apoi noduri coloana1- noroduri coloana 2, si noduri coloana 2-destinatie)
// calculand fluxul minim pe care il trimit, de la s la t
    while(!q.empty()){
        int x = q.front();
        q.pop();

        for(int i = 0; i < muchii[x].size(); i++){
            int vecin = muchii[x][i];

            if(tata[vecin] == -1 && flux[x][vecin] < capacitate[x][vecin]){
                tata[vecin] = x;

                if(f_min > capacitate[x][vecin] - flux[x][vecin])
                    f_min = capacitate[x][vecin] - flux[x][vecin];

                if(destinatie == vecin)
                    return f_min;

                q.push(vecin);
            }
        }
    }

    return 0;
}

int main(){
    f >> nr_noduri;

    sursa = 0;
    destinatie = 2 * nr_noduri + 1;

    vector<int> tata(destinatie + 1, -1);
    vector<vector<int>> muchii(destinatie + 1);
    vector<vector<int>> flux(destinatie + 1, vector<int>(destinatie + 1, 0));
    vector<vector<int>> capacitate(destinatie + 1, vector<int>(destinatie + 1, 0));

    for(int i = 1; i <= nr_noduri; i++){
        f >> ies >> intra;

        muchii[i].push_back(sursa); // sursa are muchie cu fiecare nod 1..n din coloana 1
        muchii[sursa].push_back(i);
        capacitate[sursa][i] = ies;   // cat trec pe muchii de la sursa la nodurile 1..n din coloana 1

        for(int j = 1; j <= nr_noduri; j++)
            if(i != j){
                muchii[i].push_back(j + nr_noduri);  // fiecare nod 1..n din coloana 1 are muchie cu nodurile n+1..n+n din coloana 2
                muchii[j + nr_noduri].push_back(i); // si invers , dar fara bucla ( daca n= 4, nu am muchie 1-5, 2-6..)
                capacitate[i][j + nr_noduri] = 1; // capacitatile intre fiecare = 1
            }

        muchii[i + nr_noduri].push_back(destinatie); // fiecare nod n+1..n+n din coloana 2 are legatura cu destinatia
        muchii[destinatie].push_back(i + nr_noduri);
        capacitate[i + nr_noduri][destinatie] = intra; // capacitatea fiind nr de muchii care intra
    }

   nr_muchii = 0;
    while(1){  // cat timp mai am ce sa trimit
        int f = bfs(sursa, destinatie, tata, muchii, capacitate, flux); // cat pot trimite minim de la s la t

        if(f){
            nr_muchii += f;
             // parcurs drumul t->s ajutandu-ma de vectorul de tati pentru a completa matricea de flux
            int x = destinatie;
            while(x != sursa){
                int y = tata[x];  // adaug la fiecare pas cantitatea de marfa trimisa de la s la t
                flux[y][x] += f;    // pe fiecare muchie care alcatuieste acest drum
                flux[x][y] -= f; // indic cat pot trimite si invers
                x = y;
            }
        }
        else
            break;
    }

    g << nr_muchii << endl;
    for(int i = 1; i <= nr_noduri; i++)
        for(int j = 1; j <= nr_noduri; j++)
            if(flux[i][j + nr_noduri])
                g << i << ' ' << j << endl;

    return 0;
}