Cod sursa(job #2958421)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 26 decembrie 2022 15:08:15
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");

int n, in[101], out[101], capacitate[202][202], sursa, destinatie, parinte[202];
vector<int> muchii[202];

void citeste(), construiesteGrafulDeFlow(), afiseazaMuchiile();
int edmondsKarp();

int main()
{
    citeste();
    construiesteGrafulDeFlow();
    g << edmondsKarp() << '\n';
    afiseazaMuchiile();
    return 0;
}

void afiseazaMuchiile()
{
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(i != j && capacitate[i][n + j] == 0)
                g << i << " " << j << '\n';
}

bool bfs()
{
    vector<bool> ap;
    queue<int> q;
    ap.resize(destinatie + 1);
    // Adaug sursa in coada
    q.push(sursa);
    ap[sursa] = true;
    // Cat timp mai am elemente in coada
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        // Verific daca pot sa mai pun flow pe muchiile catre vecinii nodului curent
        for(auto it : muchii[nod]){
            // Daca vecinul nu e vizitat si se poate adauga flow pe muchia de la nod la el
            if(!ap[it] && capacitate[nod][it]){
                // Parintele vecinului este nodul curent si vecinul e vizitat si adaugat in coada
                parinte[it] = nod;
                ap[it] = true;
                q.push(it);
                // Daca vecinul este destinatia atunci am gasit un drum bun
                if(it == destinatie)
                    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()) {
        // Adaug la toate muchiile de pe drum 1
        int nod = destinatie;
        while(nod != sursa) {
            int par = parinte[nod];
            capacitate[par][nod] -= 1;
            capacitate[nod][par] += 1;
            nod = par;
        }
        // Adaug flow-ul gasit la raspuns
        raspuns += 1;
    }
    return raspuns;
}

void construiesteGrafulDeFlow()
{
    sursa = 0;
    destinatie = 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) {
        muchii[sursa].push_back(i);
        capacitate[sursa][i] = in[i];
    }
    // Muchii de la noduri la destinatie
    for(int i = 1; i <= n; ++i) {
        muchii[n + i].push_back(destinatie);
        capacitate[n + i][destinatie] = out[i];
    }
    // Muchiile intre noduri
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(i != j) {
                muchii[i].push_back(n + j);
                muchii[n + j].push_back(i);
                capacitate[i][n + j] = 1;
            }
}

void citeste()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> in[i] >> out[i];
}