Pagini recente » Cod sursa (job #1255598) | Cod sursa (job #411928) | Cod sursa (job #2668069) | Cod sursa (job #2806990) | Cod sursa (job #2959259)
#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<int, int>> deg;
bool cmp(int a, int b) {
return deg[a] > deg[b];
}
int main() {
cin >> n;
deg.resize(n);
for(int i = 0; i < n; i++) {
cin >> deg[i].first >> deg[i].second;
}
int m = 0;
for(int i = 0; i < n; i++) m += deg[i].first;
cout << 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--;
cout << sorted[j] + 1 << ' ' << i + 1 << '\n';
}
}
}
}