Cod sursa(job #3323728)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 19 noiembrie 2025 15:35:59
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <vector>

using namespace std;
const int NMAX = 202;

struct muchie {
    int nod;
    int cap;
    int flux;
    int pereche;
};
vector <vector <muchie>> v;
int sursa, dest;

void addedge(int a, int b, int cap) {
    v[a].push_back({b, cap, 0, -1});
    v[b].push_back({a, 0, 0, -1});
    v[a].back().pereche = v[b].size() - 1;
    v[b].back().pereche = v[a].size() - 1;
}


vector <pair <int, int>> ans;
int main() {
    int n;
    cin >> n;
    sursa = 2 * n + 1, dest = 2 * n + 2;
    v.resize(dest + 1);
    for(int i = 1; i <= n; i++) {
        int intra, iese;
        cin >> intra >> iese;
        addedge(sursa, i, intra);
        addedge(n + i, dest, iese);
        for(int j = 1; j <= n; j++) {
            if(i != j)
                addedge(i, n + j, 1);
        }
    }
    while(bfs()) {
        for(int i = 0; i < v[dest].size(); i++) {
            muchie x = v[dest][i];
            if(viz[x.nod] && v[x.nod][x.pereche].flux < v[x.nod][x.pereche].cap) {
                int add = recons(x.nod, v[x.nod][x.pereche].cap - v[x.nod][x.pereche].flux);
                if(add > 0) {
                    change(x.nod, dest, x.pereche, add);
                    update(x.nod, add);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(auto x : v[i]) {
            if(x.flux == 1) {
                ans.push_back({i, x.nod});
            }
        }
    }
    cout << ans.size() << '\n';
    for(auto x : ans)
        cout << x.first << " " << x.second << '\n';
    return 0;
}