Cod sursa(job #3188983)

Utilizator AnastasiaStefanescuAnastasia Stefanescu AnastasiaStefanescu Data 4 ianuarie 2024 11:39:02
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

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

#define maxdim 203
#define max_sum_muchii 16000

int n, in[103], out[103];
int flux[maxdim][maxdim], flux_total;
int rezidual[maxdim][maxdim];
vector<vector<int>> graf;
int ult_nod, primul_nod, capacitate_reziduala;
int parinte[maxdim];

void init(){
    for (int i = 0; i<= 2*n+1; i++)
        parinte[i] = -1;
}
int exista_drum_crestere(){
    init();
    queue <int> qu;
    
    qu.push(0);
    parinte[primul_nod] = 0;
    
    while (!qu.empty()) {
           int nod = qu.front();
           qu.pop();

        for (int i = 0; i< graf[nod].size(); i++)
           {
               int nod2 = graf[nod][i];
               
               if (parinte[nod2] == -1 && rezidual[nod][nod2] > 0)
               {
                   // Daca gasim conexiune la final, se termina bfs
                   if (nod2 == 2*n+1) {
                       //parinte[nod2] = nod;
                       return 1;
                   }
                   qu.push(nod2);
                   parinte[nod2] = nod;
               }
           }
       }
    return 0;
}

void pt_fiec_nod(int k){
    capacitate_reziduala = max_sum_muchii;
    parinte[ult_nod] = k;

    int nod = ult_nod, prev;
    while(nod!= primul_nod && capacitate_reziduala > 0)
    {
        prev = parinte[nod];
        if(rezidual[prev][nod] < capacitate_reziduala)
            capacitate_reziduala = rezidual[prev][nod];
        nod = prev;
    }
    nod = ult_nod;
    while(nod!= primul_nod && capacitate_reziduala > 0)
    {
        prev = parinte[nod];
        rezidual[nod][prev] += capacitate_reziduala;
        rezidual[prev][nod] -= capacitate_reziduala;
        nod = prev;
    }
    flux_total += capacitate_reziduala;
}

void update(){
    int i;
    //ne uitam la toate drumurile valide pe care le-am gasit si pt fiecare gasim capacitatea reziduala
    for (i = n+1; i <= 2*n; i++)
    {
        pt_fiec_nod(i);
    }
}
int main()
{
    //nodul de start n punem 0, finalul este 2*n+1
    int i,j;
    
    fin >> n;
    ult_nod = 2*n+1;
    primul_nod = 0;
    for (i = 1; i<= n; i++)
        fin >> out[i] >> in[i];
    
    graf.resize(maxdim);
    for(i = 1; i<= n; i++) //primul rand de noduri
    {
        //flux[primul_nod][i] = out[i];
        rezidual[primul_nod][i] = out[i];
        graf[i].push_back(primul_nod);
        graf[primul_nod].push_back(i);
        
        for (j = n+1; j<= 2*n; j++)
            if(j - n != i)
            {
                rezidual[i][j] = 1;
                graf[i].push_back(j);
                graf[j].push_back(i);
            }
        
        rezidual[n+i][ult_nod] = in[i];
        graf[n+i].push_back(ult_nod);
        graf[ult_nod].push_back(n+i);
    }
    
    while (exista_drum_crestere()) 
    {
        update();
    }
    
    fout << flux_total << '\n';

    for (i = 1; i<= n; i++)
        for (j = n+1; j<= 2*n; j++)
            if( i != j - n && rezidual[i][j] == 0)
                fout << i << " " << j-n << '\n';
    
    return 0;
}