Cod sursa(job #3188823)

Utilizator theo_scrie_codGhinea Theodor theo_scrie_cod Data 3 ianuarie 2024 21:32:43
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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


int nod_start, nod_final;

vector<vector<int>> flow(202, vector<int>(202, 0));
vector<vector<int>> capacitate(202, vector<int>(202, 0));
vector<int> temp_flow(202, 0); //pe arc
vector<int> tati(202, -1);
vector<vector<int>> vecini(202);

queue<int> que;

int BFS()
{
    fill(tati.begin(), tati.end(), -1);
    tati[nod_start] = 0;
    fill(temp_flow.begin(), temp_flow.end(), 0);

    int current;
    //clear the que
    while (!que.empty())
    {
        que.pop();
    }
    que.push(nod_start);
    // sa nu fie 1000 prea mic
    temp_flow[nod_start] = 10000;

    

    while(!que.empty())
    {
        current = que.front();
        que.pop();

        for(int vecin : vecini[current])
        {
            
            if(tati[vecin] == -1 && capacitate[current][vecin] - flow[current][vecin] > 0)
            {
                tati[vecin] = current;
                
                temp_flow[vecin] = min(temp_flow[current],(capacitate[current][vecin] - flow[current][vecin]));

                if(vecin == nod_final) 
                    return temp_flow[nod_final];
                
                que.push(vecin);
        
            }
            
            
        }
    }

    return 0;
}

int main(){

    int n;
    f >> n;
    nod_final = 2 * n + 1;

    

    for(int i = 1 ; i <= n; i++)
    {
        int out, in;
        f >> out >> in;

        capacitate[nod_start][i] = out;
        capacitate[i + n][nod_final] = in;

        vecini[nod_start].push_back(i);
        vecini[n + i].push_back(nod_final);

        // legam nodurile de la 1 la n cu cele de la n + 1 la 2n si le dam capacitatea 1
        for(int j = n + 1; j <= n*2; j++)
        {
            //pentru a evita sa legam nodul de el insusi
            if(j != i+n)
            {
                capacitate[i][j] = 1;
                vecini[i].push_back(j);
                vecini[j].push_back(i);
            }
        }
    }

    int flux_max = 0;

    fill(flow.begin(), flow.end(), vector<int>(202, 0));
    while(true) {

        int flux = BFS();

        if (flux == 0) {break;}

        flux_max += flux;

        int nod = nod_final;

        //pusham flowul pe drumul gasit
        while (nod != nod_start)
        {
            flow[ tati[nod] ][nod] += flux;
            flow[nod][tati[nod] ] -= flux;
            nod = tati[nod];
        }
    }
    g << flux_max << endl;

    for(int i = 1; i <= n; i++)
        for(int j = 1 + n; j <= n * 2; j++)
            if(flow[i][j])
                g << i << ' ' << j - n << endl;



    return 0;

}