Cod sursa(job #2959260)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 30 decembrie 2022 13:23:41
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
vector<pair<int, int>> deg;

bool cmp(int a, int b) {
    return deg[a] > deg[b];
}

int main() {
    fin >> n;

    deg.resize(n);
    for(int i = 0; i < n; i++) {
        fin >> deg[i].first >> deg[i].second;
    }

    int m = 0;
    for(int i = 0; i < n; i++) m += deg[i].first;
    fout << m << '\n';

    vector<int> sorted(n);
    for(int i = 0; i < n; i++) sorted[i] = i;

    // greedy? in O(n^2 * log n)
    // sortam la fiecare pas nodurile descrescator in functie de gradul ramas
    // iar apoi cuplam cate 2 noduri daca au gradele > 0
    for(int i = 0; i < n; i++) {
        sort(sorted.begin(), sorted.end(), cmp);
        for(int j = 0; j < n; j++) {
            if(i != sorted[j] && deg[sorted[j]].first > 0 && deg[i].second > 0) {
                deg[sorted[j]].first--;
                deg[i].second--;
                fout << sorted[j] + 1 << ' ' << i + 1 << '\n';
            }

        }
    }
}