Cod sursa(job #2967906)

Utilizator EdgarPaun Andrei Edgar Data 20 ianuarie 2023 12:24:37
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.91 kb
// Complexitate: O(n * m^2)
#include <bits/stdc++.h>

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

int n, in[101], out[101], capGrafRezidual[202][202], newSource, newDestination, tata[202];
vector<int> listaAdiacenta[202];


bool bfs() {
    vector<bool> vizitat;
    queue<int> q;
    vizitat.resize(newDestination + 1);
    q.push(newSource);
    vizitat[newSource] = true;

    while(!q.empty()){
        int nod = q.front();
        q.pop();
        for(auto vecin : listaAdiacenta[nod]){
            // Daca vecinul nu e vizitat si se poate adauga flow pe muchia de la nod la el (capacitatea e mai mare decat 0)
            if(!vizitat[vecin] && capGrafRezidual[nod][vecin]){
                // Este updatat vectorul tata pentru a putea reconstrui drumul de ameliorare
                tata[vecin] = nod;
                vizitat[vecin] = true;
                q.push(vecin);
                // Daca vecinul este destinatia atunci am gasit un drum bun 
                // BFS-ul este optimizat pentru ca el se incide direct cand vecinul este destinatia
                if(vecin == newDestination)
                    return true;
            }
        }
    }
    return false;
}


int edmondsKarp()
{
    int raspuns = 0;
    // Cat timp mai gasesc un drum pana la destinatie pe care pot adauga flow
    while(bfs()) {
        int nod = newDestination, bottleNeck = 1000000000;
        while(nod != newSource) {
            int parinte = tata[nod];
            if(capGrafRezidual[parinte][nod] < bottleNeck) {
                // Este calculata valoarea minima de pe drumul respectiv (bottleNeck), de la destinatie la sursa
                // folosind vectorul tata
                bottleNeck = capGrafRezidual[parinte][nod];
            }
            nod = parinte;
        }
        // Adaug la toate muchiile de pe drum flow-ul maxim
        nod = newDestination;
        while(nod != newSource) {
            int parinte = tata[nod];
            capGrafRezidual[parinte][nod] -= bottleNeck; // Drum direct in graful rezidual
            capGrafRezidual[nod][parinte] += bottleNeck; // Drum invers in graful rezidual
            nod = parinte;
        }
        // Adaug flow-ul gasit la raspuns
        raspuns += bottleNeck;
    }
    return raspuns;
}


int main()
{
    

    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> in[i] >> out[i];


    newSource = 0;
    newDestination = 2 * n + 1;


    // Muchiile intermediare
    // Nodurile sunt trecute in 2 multimi, una care e conectata de sursa si una care e conectata de destinatie
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(i != j) {
                listaAdiacenta[i].push_back(n + j);
                listaAdiacenta[n + j].push_back(i);
                capGrafRezidual[i][n + j] = 1;
            }

    // Muchii de la sursa la nodurile din prima multime
    for(int i = 1; i <= n; ++i) {
        listaAdiacenta[newSource].push_back(i);
        capGrafRezidual[newSource][i] = in[i]; // gradele de iesire
    }
    // Muchii de la noduri la destinatie
    for(int i = 1; i <= n; ++i) {
        listaAdiacenta[n + i].push_back(newDestination);
        capGrafRezidual[n + i][newDestination] = out[i]; //gradele de intrare
    }
    

    fout << edmondsKarp() << '\n';

    //Muchiile construite
    // Arcele care au flux pozitiv sunt muchiile construite

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(capGrafRezidual[n+j][i] == 1)
                fout << i << " " << j << '\n';

    /*
    Există graf cu secvenţele date <=> în rețeaua asociată fluxul de valoare maximă are 
    val(f)=𝑑1+ + ... + 𝑑𝑛+ = 𝑑1− + ... + 𝑑𝑛− (saturează toate arcele care ies din s și toate arcele care intră în t )
    tăieturile({s},V-{s}),(V-{t},{t})sunt minime
    */


    return 0;
}