Cod sursa(job #3361211)

Utilizator SkibidiCezarCezar Bolba SkibidiCezar Data 21 iulie 2026 18:10:04
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <bits/stdc++.h>
#define f first
#define s second

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

int n, m, maxflux;
pair <int, int> drum;
struct much{
    int a, b, c, f;
};
vector <much> a;
vector <int> v[205];
int last[205];
queue <int> q;

void bfslave(){
    for(int i = 0; i <= 2 * n + 1; i++){
        last[i] = -1;
    }
    last[0] = -2;
    q.push(0);
    int nod;
    much nxt;
    while(!q.empty()){
        nod = q.front();
        q.pop();
        for(int i = 0; i < v[nod].size(); i++){
            nxt = a[v[nod][i]];
            if(nod != 2 * n + 1 && nxt.f < nxt.c && last[nxt.b] == -1){
                last[nxt.b] = v[nod][i];
                q.push(nxt.b);
            }
        }
    }
}

void fa_un_drum(){
    int nod = 2 * n + 1;
    int minim_ude = INT_MAX;
    while(last[nod] != -2){
        minim_ude = min(minim_ude, a[last[nod]].c - a[last[nod]].f);
        nod = a[last[nod]].a;
    }
    maxflux += minim_ude;
    nod = 2 * n + 1;
    while(last[nod] != -2){
        a[last[nod]].f += minim_ude;
        a[(last[nod]+m)%(2*m)].f -= minim_ude;
        nod = a[last[nod]].a;
    }
}

void fa_drumurile(){
    int mettaton;
    for(int i = 0; i < v[2*n+1].size(); i++){
        mettaton = v[2*n+1][i];
        if(last[a[mettaton].b] != -1){
            last[2*n+1] = mettaton - m;
            fa_un_drum();
        }
    }
}

void flux(){
    int lastflux = -1;
    while(lastflux != maxflux){
        lastflux  = maxflux;
        bfslave();
        fa_drumurile();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> drum.f >> drum.s;
        a.push_back({0, i, drum.f, 0});
        a.push_back({i + n, 2 * n + 1, drum.s, 0});
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i != j){
                a.push_back({i, j + n, 1, 0});
            }
        }
    }
    m = a.size();
    for(int i = 0; i < m; i++){
        v[a[i].a].push_back(i);
        a.push_back({a[i].b, a[i].a, 0, 0});
        v[a[i].b].push_back(i + m);
    }
    flux();
    fout << maxflux << "\n";
    for(int i = 2 * n; i < m; i++){
        if(a[i].f == a[i].c){
            fout << a[i].a << " " << a[i].b - n << "\n";
        }
    }
    return 0;
}