Cod sursa(job #3190495)

Utilizator AlexTrandafir09Trandafir Alexandru Ionut AlexTrandafir09 Data 7 ianuarie 2024 17:37:03
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream f("../harta.in");
ofstream g("../harta.out");

int n, x, y, nr_drumuri;
vector<vector<int>> vecini, capacitati, flow;
int nod_sursa, nod_final;
vector<int> predecesor;

int bfs () {
    for(int i=0; i <= nod_final; i++){
        predecesor[i] = -1; //in vectorul predecesor salvam cel mai scurt drum gasit de bfs
    }
    queue<pair<int, int>> q; //pereche de nod-flow minim pana in acel punct
    q.push({0, INT_MAX});
    while (!q.empty()) {
        int oras = q.front().first, flow_min_anterior = q.front().second;
        q.pop();
        for (auto& urm_oras : vecini[oras]) {
            if (predecesor[urm_oras] == -1 && capacitati[oras][urm_oras] > flow[oras][urm_oras]) { // daca nu e vizitat deja si daca capacitatea permite sa mergem
                predecesor[urm_oras] = oras;
                int flow_min_actual = capacitati[oras][urm_oras] - flow[oras][urm_oras];
                int flow_min;
                if (flow_min_anterior > flow_min_actual) //actualizam flowul minim prin compararea flowului minim de la nodul anterior cu capacitatea residuala a nodului actual
                    flow_min=flow_min_actual;
                    //q.push({urm_oras,flow_min_actual});
                else
                    flow_min=flow_min_anterior;
                    //q.push({urm_oras,flow_min_actual});
                q.push({urm_oras, flow_min});

                if (urm_oras == nod_final) return flow_min;
            }
        }

    }
    return 0;
}
void edmonds_karp () {
    int oras_act, oras_ant;
    while (true) {
        int flow1 = bfs();
        if (!flow1) break;
        oras_act = nod_final;//parcurgem drumul gasit cu bfs in ordine inversa cu ajutorul vectorului predecesor
        while (nod_sursa != oras_act) {
            oras_ant = predecesor[oras_act];
            flow[oras_act][oras_ant] -= flow1;
            flow[oras_ant][oras_act] += flow1;

            oras_act = predecesor[oras_act];
        }
    }
}

void citire_date () {
    f >> n;
    nod_final = 2 * n + 1;
    predecesor.resize(nod_final);
    vecini.resize(nod_final + 1, {});
    capacitati.assign(nod_final + 1, vector<int>(nod_final + 1));
    flow.resize(nod_final + 1, vector<int>(nod_final + 1));

    for (int i=1; i <= n; i++) {
        f>>x>>y;
        nr_drumuri += x;
        for (int j=1; j <= n; j++) {
            if (i != j) {
                vecini[j + n].push_back(i);
                vecini[i].push_back(j + n);
                capacitati[i][j + n] = 1;
            }
        }
        capacitati[nod_sursa][i] = x;
        capacitati[i + n][nod_final] = y;
        vecini[nod_sursa].push_back(i);
        vecini[i].push_back(nod_sursa);
        vecini[i + n].push_back(nod_final);
        vecini[nod_final].push_back(i + n);
    }
}


int main () {
    citire_date();
    g << nr_drumuri << endl;
    edmonds_karp();
    for (int i=1; i <= n; i++) {
        for (int j= n + 1; j < nod_final; j++) {
            if (flow[i][j]) {
                g << i << " " << j - n << endl;
            }
        }
    }
    return 0;
}