Cod sursa(job #3188039)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 1 ianuarie 2024 13:12:01
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.94 kb
//ALEXANDRU MICLEA
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

//VARIABLES

int inf = 1e9 + 7;
int n, m;

int capacitate[205][205];
int flux[205][205];
int flux_pe_nod[205];
int tata[205];
int nod_terminal;

vector<int> gr[205];
queue<int> q;

//FUNCTIONS

int drum_ameliorare() {
    for(int i = 0; i <= nod_terminal; i++){
        tata[i] = -1;
    }

    tata[0] = -2;
    flux_pe_nod[0] = inf;
    while (!q.empty()) q.pop();
    q.push(0);

    while (!q.empty()) {
        int nod_curent = q.front();
        q.pop();

        for (auto& nod_adiacent : gr[nod_curent]){
            if (tata[nod_adiacent] == -1 && capacitate[nod_curent][nod_adiacent] - flux[nod_curent][nod_adiacent] > 0) {
                tata[nod_adiacent] = nod_curent;
                flux_pe_nod[nod_adiacent] = min(flux_pe_nod[nod_curent], capacitate[nod_curent][nod_adiacent] - flux[nod_curent][nod_adiacent]);
                if (nod_adiacent == nod_terminal) return flux_pe_nod[nod_adiacent];
                q.push(nod_adiacent);
            }
        }
    }

    return 0;
}

//MAIN
int main() {

//#define FILE_INPUT
#ifdef INFOARENA
    ifstream fin("harta.in"); ofstream fout("harta.out");
    cin.rdbuf(fin.rdbuf()); cout.rdbuf(fout.rdbuf());
#endif
#ifdef FILE_INPUT
    ifstream fin("file.in"); cin.rdbuf(fin.rdbuf());
    ofstream fout("file.out"); cout.rdbuf(fout.rdbuf());
#endif

    cin >> n;
    nod_terminal = 2 * n + 1;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y; // grad exterior -> grad interior
        capacitate[0][i] += x;
        capacitate[n + i][2*n + 1] += y;
        gr[0].push_back(i);
        gr[i].push_back(0);
        gr[2*n + 1].push_back(n + i);
        gr[n + i].push_back(2 * n + 1);
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (j == i) continue;
            capacitate[i][n+j] = 1;
            gr[i].push_back(n + j);
            gr[n + j].push_back(i);
        }
    }

    // aici urmeaza sa fac flux
    int flux_total = 0;
    int flux_nou;
    while (flux_nou = drum_ameliorare()){
        flux_total += flux_nou;
        int nod_curent = nod_terminal;

        while (nod_curent != 0) {
            int nod_precedent = tata[nod_curent];
            flux[nod_curent][nod_precedent] -= flux_nou;
            flux[nod_precedent][nod_curent] += flux_nou;
            nod_curent = nod_precedent;
        }
    }

    vector <pair<int,int>> ans;

    for (int i = 1; i <= n; i++) {
        for (int j = n + 1; j <= 2 * n; j++) {
            int ii = (i > n) ? i - n : i;
            int jj = (j > n) ? j - n : j;
            if (flux[i][j]) {
                ans.push_back({ii,jj});
                flux[i][j]--;
            }
        }
    }

    cout << ans.size() << '\n';
    for (auto& x : ans) cout << x.first << ' ' << x.second << '\n';

    return 0;
}