Cod sursa(job #3190633)

Utilizator Andry101Dog Meat Andry101 Data 7 ianuarie 2024 19:37:40
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

ifstream file_in("harta.in");
ofstream file_out("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>> graph;
int last, first, rezidual_capacity;
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[first] = 0;

    while (!qu.empty()) {
        int nod = qu.front();
        qu.pop();

        for (int i = 0; i< graph[nod].size(); i++)
        {
            int nod2 = graph[nod][i];

            if (parinte[nod2] == -1 && rezidual[nod][nod2] > 0)
            {
                if (nod2 == 2*n+1) {
                    return 1;
                }
                qu.push(nod2);
                parinte[nod2] = nod;
            }
        }
    }
    return 0;
}

void pt_fiec_nod(int k){
    rezidual_capacity = max_sum_muchii;
    parinte[last] = k;

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

void update(){
    int i;
    for (i = n+1; i <= 2*n; i++)
    {
        pt_fiec_nod(i);
    }
}
int main()
{
    int i,j;

    file_in >> n;
    last = 2*n+1;
    first = 0;
    for (i = 1; i<= n; i++)
        file_in >> out[i] >> in[i];

    graph.resize(maxdim);
    for(i = 1; i<= n; i++)
    {
        rezidual[first][i] = out[i];
        graph[i].push_back(first);
        graph[first].push_back(i);

        for (j = n+1; j<= 2*n; j++)
            if(j - n != i)
            {
                rezidual[i][j] = 1;
                graph[i].push_back(j);
                graph[j].push_back(i);
            }

        rezidual[n+i][last] = in[i];
        graph[n+i].push_back(last);
        graph[last].push_back(n+i);
    }

    while (exista_drum_crestere())
    {
        update();
    }

    file_out << 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)
                file_out << i << " " << j-n << '\n';

    return 0;
}