Cod sursa(job #3306580)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 12 august 2025 12:54:33
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 101;
int n, out[NMAX], in[NMAX];
bool drum[NMAX][NMAX];
vector<pair<int, int>> drumuri;

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> out[i] >> in[i];
    fout << accumulate(out + 1, out + n + 1, 0) << "\n";
    while(true)
    {
        int sursa = -1;
        for(int i = 1; i <= n; i++)
        {
            if(out[i] > 0)
            {
                sursa = i;
                break;
            }
        }
        if(sursa == -1)
            break;
        priority_queue<pair<int, int>> pq;
        for(int dest = 1; dest <= n; dest++)
            if(dest != sursa && in[dest] > 0 && !drum[sursa][dest])
                pq.push({in[dest], dest});
        bool found = false;
        while(!pq.empty() && !found)
        {
            auto [in_deg, dest] = pq.top();
            pq.pop();
            drumuri.emplace_back(sursa, dest);
            drum[sursa][dest] = true;
            out[sursa]--;
            in[dest]--;
            found = true;
        }
    }
    for(auto [u, v] : drumuri)
        fout << u << " " << v << "\n";

    fin.close();
    fout.close();
    return 0;
}