Cod sursa(job #2962418)

Utilizator VictorB11Badulescu Victor VictorB11 Data 8 ianuarie 2023 15:36:07
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>
using namespace std;


///ex3-a infoarena harta
ifstream fin("harta.in");
ofstream fout("harta.out");
int capacitate[202][202];
vector<int> viz, tata;
int n, s = 0, t;

bool BFS()
{
    viz.clear();
    tata.clear();
    viz.resize(t + 1, 0);
    tata.resize(t + 1, 0);
    queue<int> coada;
    coada.push(s);
    viz[s] = 1;
    while(!coada.empty())
    {
        int nod = coada.front();
        coada.pop();
        if(nod == t)
            return true;

        for(int i = 1; i <= t; i++)
        {
            if(!viz[i] && capacitate[nod][i] > 0)
            {
                viz[i] = 1;
                tata[i] = nod;
                coada.push(i);
            }
        }
    }
    return false;
}
int minFlow(){
    int minflux = INT_MAX;
    for(int nod = t; nod != s; nod = tata[nod])
    {
        minflux = min(minflux, capacitate[tata[nod]][nod]);
    }
    return minflux;
}
void ex3(){
    fin >> n;
    t = 2 * n + 1;
    for(int i = 1; i <= n; i++)
    {
        int x, y;
        fin >> x >> y;
        capacitate[s][i] = x;
        capacitate[i+n][t] = y;
        for(int j = 1; j <= n; j++)
            if(i != j)
                capacitate[i][j+n] = 1;
    }
    int maxflow = 0;
    while(BFS()){
        for(int i = n + 1 ; i <= 2 * n; i++){
            if(!viz[i] || capacitate[i][t] == 0)
                continue;
            tata[t] = i;
            int minflux = minFlow();
            if(minflux == 0)
                continue;
            for(int nod = t; nod != s; nod = tata[nod])
            {
                capacitate[tata[nod]][nod] -= minflux;
                capacitate[nod][tata[nod]] += minflux;
            }
            maxflow += minflux;
        }
    }
    fout << maxflow << "\n";
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            if (capacitate[i][j + n] == 0 && i != j)
                fout << i << " " << j << "\n";
        }
}

int main() {
    ex3();
    return 0;
}