Cod sursa(job #3187595)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 29 decembrie 2023 17:19:45
Problema Taramul Nicaieri Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.08 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 tata[205];

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

//FUNCTIONS

int drum_ameliorare() {
    //cout << "in\n";
    for (auto& x : tata) x = -1;

    tata[0] = -2;
    q.push(0);
    int ok = 0;

    while (!q.empty()){
        int nod = q.front();
        //cout << nod << ' ';
        q.pop();
        if (nod == 2*n+1) {
            ok = 1;
            continue;
        }

        for (auto& x : gr[nod]) {
            if (tata[x] == -1 && capacitate[nod][x] - flux[nod][x] > 0){
                tata[x] = nod;
                q.push(x);
            }
        }
    }

    //cout << "\nout\n";
    return ok;
}

//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());
#endif

    cin >> n;
    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);
            // TODO see if this is correct
        }
    }
    // daca am n = 1 ? :)
    if (n == 1) {
        cout << 0;
        return 0;
    }

    while (drum_ameliorare()) {
        for (auto& x : gr[2*n+1]){
            if (!tata[x]) continue;
            tata[2*n + 1] = x;
            //cout << "in while\n";
            int nod_curent = 2*n + 1;
            int flux_minim = inf;


            while (nod_curent != 0) {
                //cout << nod_curent << ' ' << tata[nod_curent] << '\n';
                flux_minim = min(flux_minim, capacitate[tata[nod_curent]][nod_curent] - flux[tata[nod_curent]][nod_curent]);
                nod_curent = tata[nod_curent];
            }

            nod_curent = 2 * n + 1;

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

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