Cod sursa(job #2961141)

Utilizator Andoss1710Balanica Andrei Andoss1710 Data 5 ianuarie 2023 21:41:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.99 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

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

int n;
vector<vector<int>> lista(305);
int cap[205][205];
int cap_init[205][205];
int viz[205], tata[205];//ca sa retin nodurile vizitate si tatal nodurilor pentru reconstruirea drumului

int bfs(){//bfs pentru aflarea existentei drumului de crestere
    queue<int> coada;
    coada.push(0);
    for(int i = 0; i <= 2*n+1; i++){
        tata[i] = -1;
        viz[i] = 0;
}
    viz[0]++;

    while(coada.size()!=0){
        int nod_cur = coada.front();
        if(nod_cur == 2*n+1)//daca am ajuns la final inseamna ca am gasit un drum de crestere
            return 1;
        for(int i = 0; i < lista[nod_cur].size(); i++){
            int nod_vec = lista[nod_cur][i];
            if(cap[nod_cur][nod_vec] > 0 && viz[nod_vec] == 0){//daca am gasit un nod prin care nu am mai fost care mai are loc, trecem prin el
                viz[nod_vec]++;
                tata[nod_vec] = nod_cur;
                coada.push(nod_vec);

            }
        }
        coada.pop();//scot din coada nodul prin care deja am trecut
    }
    return 0;//nu am gasit
}

int Edmonds_Karp(){
    int max_flux = 0;//fluxul maixim
    while(bfs()){//cat timp avem drum de crestere
        for(int i = 0; i < lista[2*n+1].size(); i++){
            int nod_cur = lista[2*n+1][i];
            if(cap[nod_cur][2*n+1] > 0 && viz[nod_cur]){//daca este drum care a dus de la vecinul lui n la n care mai are capacitate
                    //si a fost vizitat in verificarea noastra, atunci reconstituim drumul parcurs
               //cout<<nod_cur<<" ";
               vector<int> drum;//reconstituirea drumului
               drum.push_back(nod_cur);

               while(tata[nod_cur]!=-1){
                nod_cur = tata[nod_cur];
                drum.push_back(nod_cur);
               }
                int minim = 9999999;//bottleneckul nostru

               for(int i = 0; i < drum.size(); i++)//vedem care este bottleneckul drumului
                    if(i == 0)
                        minim = min(minim, cap[drum[i]][2*n+1]);
                    else
                         minim = min(minim, cap[drum[i]][drum[i-1]]);

                max_flux += minim;//il adaugam la flux doarece e cea mai mare valoare pe care o putem trece prin acel drum
                for(int i = 0; i < drum.size(); i++){
                    if(i == 0){
                        cap[drum[i]][2*n+1] -= minim;//scadem cap de la muchia de crestere
                        cap[2*n+1][drum[i]] +=minim;//dar crestem cap muchiei de intoarece
                    }
                    else{
                        cap[drum[i]][drum[i-1]] -= minim;
                        cap[drum[i-1]][drum[i]] += minim;
                    }

                }
                //cout<<minim<<" ";
            }
        }

    }
    return max_flux;//fluxul maxim

}
int main()
{
    fin>>n;
    for(int i = 1; i <= n; i++){
        int x, y;
        fin>>x>>y;
        lista[0].push_back(i);
        lista[1].push_back(0);
        cap[0][i] = x;
        cap_init[0][i] = x;
        lista[n+i].push_back(2*n+1);
        lista[2*n+1].push_back(n+i);
        cap[n+i][2*n+1] = y;
        cap_init[n+i][2*n+1] = y;
    }

    for(int i = 1; i <= n; i++)
        for(int j = n+1; j < 2*n+1; j++){
            if((i+n)!=j){
                lista[i].push_back(j);
                lista[j].push_back(i);
                cap[i][j] = 1;
                cap_init[i][j] = 1;
            }
    }
//    for(int i = 0; i <= 2*n+1; i++){
//            for(int j = 0; j <= 2*n+1; j++)
//                cout<<cap[i][j]<<" ";
//            cout<<endl;
//            }
//            cout<<endl;
    fout<<Edmonds_Karp()<<"\n";
    for(int i = 1; i <= n; i++)
        for(int j = n+1; j < 2*n+1; j++)
            if(cap_init[i][j] == 1 && cap[i][j] == 0)
                fout<<i<<" "<<j-n<<"\n";

}