Cod sursa(job #3189332)

Utilizator Andrei34Munteanu Andrei Andrei34 Data 4 ianuarie 2024 20:57:58
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

vector<vector<int>> capacitate;
vector<vector<int>> flux;
vector<bool> viz;
vector<int> tata;

bool BFS(int s, int t){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        viz[nod] = true;

        for(int i=0; i<t+1; i++){
            if(!viz[i] && capacitate[nod][i] - flux[nod][i] > 0){
                q.push(i);
                tata[i] = nod;
                viz[i] = true;
            }
        }
    }
    return viz[t];
}

int main() {
    int n;
    fin>>n;
    tata.resize(2*n+2, -1);
    viz.resize(2*n+2, false);
    flux.resize(2*n+2, vector<int>(2*n+2, 0));
    capacitate.resize(2*n+2, vector<int>(2*n+2, 0));

    int s = 2*n, t=2*n+1;
    for(int i=0; i<n; i++){
        int x, y;
        fin >> x >> y;
        capacitate[s][i] = x;
        capacitate[n+i][t] = y;

        for(int j=0; j<n; j++)
            if(i != j)
                capacitate[i][n+j] = 1;
    }

    int flux_maxim = 0;
    while(BFS(s, t)){
        int cap_minima = INT_MAX;
        int nod1 = tata[t], nod2 = t;
        while(nod1 != -1){
            int cap = capacitate[nod1][nod2] - flux[nod1][nod2];
            if(cap < cap_minima)
                cap_minima = cap;

            nod2 = nod1;
            nod1 = tata[nod1];
        }

        nod1 = tata[t], nod2 = t;
        while(nod1 != -1){
            flux[nod1][nod2] += cap_minima;
            flux[nod2][nod1] -= cap_minima;
            nod2 = nod1;
            nod1 = tata[nod1];
        }
        flux_maxim += cap_minima;

        for(int i=0; i<2*n+2; i++) {
            viz[i] = false;
        }
    }

    fout<<flux_maxim<<endl;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            if(flux[i][n+j] == 1) {
                fout<<i+1<<' '<<j+1<<endl;
            }
        }
    return 0;
}