Cod sursa(job #2962364)

Utilizator AdelaCorbeanuAdela Corbeanu AdelaCorbeanu Data 8 ianuarie 2023 14:10:19
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,flux;
vector<vector<int>> adiacenta, capacitate;
vector<bool> vizitat;
vector<int> tata;
bool bfs(){
    // cu bfs cautam in graful rezidual daca exista un drum din sursa pana in destinatie
    queue<int> coada;
    vizitat.clear();
    tata.clear();
    vizitat.resize(2*n+2,false);
    tata.resize(2*n+2,0);

    coada.push(0);
    vizitat[0]=true;
    while(!coada.empty()){
        int nod=coada.front();
        coada.pop();
        if(nod==2*n+1)
            return true;
        for (int i = 0; i < adiacenta[nod].size(); ++i) {
            if(!vizitat[adiacenta[nod][i]] && capacitate[nod][adiacenta[nod][i]]>0){
                tata[adiacenta[nod][i]]=nod;
                coada.push(adiacenta[nod][i]);
                vizitat[adiacenta[nod][i]]=true;
            }
        }
    }
    return false;
}
int main(){
    // Complexitatea este de O(n*m*m)
    // Ideea se bazeaza pe algoritmul Edmonds-Karp
    // Dublam fiecare nod si le memoram de la 1 la n si de la n+1 la 2*n
    // Adaugam un nod sursa numerotat cu 0 si un nod destinatie 2*n+1
    int x,y;
    f>>n;

    adiacenta.resize(2*n+2);
    capacitate.resize(2*n+2,vector<int>(2*n+2,0));
    // Adaugam muchie intre sursa si toate nodurile (prima multime) cu capacitate gradul pentru iesire
    // Si muchie intre toate nodurile (a doua multime) si destinatie cu capacitate gradul pentru intrare
    // Apoi adaug muchie de la orice nod din prima multime la orice alt nod din a doua multime cu capacitatea 1
    for (int i = 1; i <= n; ++i) {
        f>>x>>y;
        capacitate[0][i]=x;
        capacitate[n+i][2*n+1]=y;
        adiacenta[0].push_back(i);
        adiacenta[i].push_back(0);
        adiacenta[n+i].push_back(2*n+1);
        adiacenta[2*n+1].push_back(n+i);
        for (int j = n+1; j <= 2*n; ++j) {
            if(n+i!=j){
                adiacenta[i].push_back(j);
                adiacenta[j].push_back(i);
                capacitate[i][j]=1;
            }
        }
    }

    while(bfs()){ // cat timp pot ajunge de la sursa la destinatie
        for (int i = 0; i < adiacenta[2*n+1].size(); ++i) {
            if(vizitat[adiacenta[2*n+1][i]]){ // am gasit un drum pana in destinatie care contine acest nod
                tata[2*n+1]=adiacenta[2*n+1][i];
                int minim=INT_MAX;
                for (int j = 2*n+1; j !=0 ; j=tata[j]) { // calculam minimul lantului
                    minim=min(minim,capacitate[tata[j]][j]);
                }
                for (int j = 2*n+1; j !=0 ; j=tata[j]) { // actualizam graful rezidual
                    capacitate[tata[j]][j] -= minim;
                    capacitate[j][tata[j]] += minim;
                }
                flux+= minim;
            }
        }
    }
    g<<flux<<'\n'; // fluxul maxim este numarul de muchii adaugate
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < adiacenta[i].size(); ++j) {
            if(capacitate[i][adiacenta[i][j]]==0) // muchiile sunt cele saturate
                g<<i<<' '<<adiacenta[i][j]-n<<'\n';
        }
    }
    return 0;
}