Pagini recente » Cod sursa (job #580142) | Cod sursa (job #2641638) | Cod sursa (job #2663707) | Cod sursa (job #362019) | Cod sursa (job #2959260)
#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';
}
}
}
}