Cod sursa(job #2962037)

Utilizator mikkiMihai Pricope mikki Data 7 ianuarie 2023 17:46:57
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.48 kb
#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;
            }
        }
    }
    // Daca ajung aici nu mai sunt drumuri bune
    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;
    // Sparg nodurile in doua unul care e conectat de sursa si unul care e conectat de destinatie
    // Muchii de la sursa la noduri
    for(int i = 1; i <= n; ++i) {
        listaAdiacenta[newSource].push_back(i);
        capGrafRezidual[newSource][i] = in[i];
    }
    // 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];
    }
    // Muchiile intre noduri
    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;
            }

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

    //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';
    return 0;
}