Cod sursa(job #3323808)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 19 noiembrie 2025 22:02:23
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;
const int NMAX = 202;

ifstream cin("harta.in");
ofstream cout("harta.out");

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;
}

bitset <NMAX + 2> viz;
pair <int, int> tata[NMAX + 2];
bool bfs() {
    viz = 0;
    for(int i = 1; i <= dest; i++) {
        tata[i].first = 0;
        tata[i].second = -1;
    }
    queue <int> q;
    viz[sursa] = 1;
    q.push(sursa);
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        for(int i = 0; i < v[now].size(); i++) {
            muchie x = v[now][i];
            if(!viz[x.nod] && x.flux < x.cap) {
                viz[x.nod] = 1;
                q.push(x.nod);
                tata[x.nod].first = now;
                tata[x.nod].second = i;
            }
        }
    }
    return viz[dest];
}

int recons(int nod, int minn) {
    while(tata[nod].first) {
        minn = min(minn, v[tata[nod].first][tata[nod].second].cap - v[tata[nod].first][tata[nod].second].flux);
        if(minn <= 0)
            return minn;
        nod = tata[nod].first;
    }
    return minn;
}

void change(int a, int b, int id, int val) {
    v[a][id].flux += val;
    v[b][v[a][id].pereche].flux -= val;
}

void update(int nod, int add) {
    while(tata[nod].first) {
        change(tata[nod].first, nod, tata[nod].second, add);
        nod = tata[nod].first;
    }
}


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); ///1)
        addedge(n + i, dest, iese); ///3)
        for(int j = 1; j <= n; j++) { ///2)
            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 - n});
            }
        }
    }
    cout << ans.size() << '\n';
    for(auto x : ans)
        cout << x.first << " " << x.second << '\n';
    return 0;
}