Cod sursa(job #3193726)

Utilizator bobic.teona20Bobic Teona-Christiana bobic.teona20 Data 15 ianuarie 2024 15:28:51
Problema Taramul Nicaieri Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define N_MAX 101

using namespace std;

ifstream fin("harta.in");
ofstream gout("harta.out");

vector<pair<int, int>> grad; //vectorul de grade
vector<int> graf(N_MAX);

bool compare(int a, int b)
{
    return grad[a].first > grad[b].first;
}

int main()
{
    int n;
    fin >> n;
    ///Citim graful (gradele nodurilor si aflam nr de drumuri)
    grad.resize(n);
    graf.resize(n);
    int nr_drumuri=0;
    for (int i = 0; i < n; i++)
    {
        fin >> grad[i].first >> grad[i].second;
        graf[i]=i;
        nr_drumuri+=grad[i].first;
    }
    //afisam nr de drumuri
    gout << nr_drumuri << '\n';
    ///trecem prin fiecare oras si iteram drumuri
    for (int i = 0; i < n; i++)
    {
        sort(graf.begin(), graf.end(), compare); //sortam descrescator in functie de grade
        for (int j = 0; j < n; j++)
        {// verificam daca nu mergem din orasul i in orasul i si daca mai avem posibilitatea de a crea drumuri
            //adica daca gradele celor doua orase ne permit asta
            if (i != graf[j] && grad[graf[j]].first > 0 && grad[i].second > 0)
            {//actualizam gradele si afisam muchia
                grad[graf[j]].first--;
                grad[i].second--;
                gout << graf[j] + 1 << ' ' << i + 1 << '\n';
            }

        }
    }
    return 0;
}