Cod sursa(job #3361089)

Utilizator iuli_morariuIuli Morariu iuli_morariu Data 20 iulie 2026 13:22:31
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.3 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
// #include <bits/std++.h>
#define in  fin
#define out fout

using namespace std;
const int NMAX = 105;

ifstream fin("harta.in");
ofstream fout("harta.out");

struct muchie{
    int x, y, pereche, f, c;
};

vector<muchie> mch;
pair<int, int> last[2 * NMAX];
bool mrc[2 * NMAX]; // 2 * NMAX pt ca am 2 layere de cate n si dupa sursie si noelle
int sursie, noelle;
// get it? sursa + susie = sursie? get it?

vector<int> g[2 * NMAX];

int n, m;

void fa_bfs_pls(){
    for(int i = 1; i <= 2 * n + 2; i++){
        mrc[i] = 0;
        last[i] = {0, -1};
    }

    queue<int> q;
    q.push(sursie);
    mrc[sursie] = 1;

    while(!q.empty()){
        int x = q.front(); q.pop();
        for(const int &cine : g[x]){
            int y = mch[cine].y;
            if(!mrc[y] && mch[cine].f < mch[cine].c){
                mrc[y] = 1;
                q.push(y);

                last[y] = {x, cine};
            }
        }
    }
}

int gaseste_minimul_pls(int nod, int minim_ude){
    while(last[nod].second != -1){
        minim_ude = min(minim_ude, mch[ last[nod].second ].c - mch[ last[nod].second ].f);
        nod = last[nod].first;
    }
    return minim_ude;
}

void satureaza_pls(int nod, int val){
    while(last[nod].second != -1){
        int id = last[nod].second; // i ain't writing allat de fiecare data
        mch[id].f += val;
        mch[ mch[id].pereche ].f -= val;

        nod = last[nod].first;
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    in >> n;
    // primii 1...n --> nodurile ca sa determin outurile
    // dupaia n + 1...2 * n --> nodurile ca sa determin inurile (ma rog asta ramane)
    // sursie = 2 * n + 1
    // noelle = 2 * n + 2

    sursie = 2 * n + 1;
    noelle = 2 * n + 2;

    for(int i = 1; i <= n; i++){
        for(int j = n + 1; j <= 2 * n; j++){
            if(i == j - n) continue;

            int id = mch.size(), idp = mch.size() + 1;
            mch.push_back({ i, j, idp, 0, 1 });
            mch.push_back({ j, i, id,  0, 0 });

            g[i].push_back(id);
            g[j].push_back(idp);
        }
    }

    vector< pair<int, int> > ralsei; // vecinii lui noelle
    // stiu ca sunt de la n + 1 la 2 * n DAR vreau si indexii in mch usor
    for(int i = 1; i <= n; i++){ // yet again, aceeasi indexare malefica
        int intra, iese; in >> iese >> intra; // pot sa intru eu in rals- cine a spus aia
        // bro lowk strid e un band destul de fain da au doar 5000 de monthly listeners TwT
        // gen ascultam in general doar sommar de la ei si credeam ca is band destul de popular ca imi place melodia
        // dar nu
        // i js put on albumul descent (cel cu sommar)
        // idk daca le pot zice dsbm da macar ceva influente is (ca bro se plange in melodii)

        int id = mch.size(), idp = mch.size() + 1;
        mch.push_back( {sursie, i, idp, 0, iese} );
        mch.push_back( {i, sursie, id,  0, 0} );

        g[sursie].push_back(id);
        g[i].push_back(idp);

        id = mch.size(), idp = mch.size() + 1;
        mch.push_back( {i + n, noelle, idp, 0, intra} );
        mch.push_back( {noelle, i + n, id,  0, 0} );

        g[i + n].push_back(id);
        g[noelle].push_back(idp);

        ralsei.push_back({i + n, id});
    }

    int total = 0;
    while(true){
        fa_bfs_pls(); // multu
        if(!mrc[noelle]) break;

        // cerr << "am ajuns!\n";

        for(const pair<int, int> &cine : ralsei){
            int y = cine.first;
            int id = cine.second;
            if(!mrc[y]) continue;
            if(mch[id].f == mch[id].c) continue;

            // cerr << "--> incerc cu y = " << y << '\n';

            int add = gaseste_minimul_pls(y, mch[id].c - mch[id].f);

            // cerr << "--> init = " << mch[id].c - mch[id].f << '\n';
            // cerr << "--> add = " << add << '\n';
            if(add == 0) continue;

            satureaza_pls(y, add);
            mch[id].f += add;
            mch[ mch[id].pereche ].f -= add;

            total += add;
        }
    }

    out << total << '\n';

    for(const muchie &x : mch){
        if(1 <= x.x && x.x <= n && n < x.y && x.y <= 2 * n && x.f == 1){
            out << x.x << " " << x.y - n << '\n';
        }
    }

    return 0;
}