Pagini recente » Cod sursa (job #1559201) | Cod sursa (job #2505651) | Cod sursa (job #2779407) | Cod sursa (job #3282659) | Cod sursa (job #3194978)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
priority_queue<pair<int,int>> intrari, iesiri;
vector<vector<int>> graf(101);
queue<pair<int, int>>rem;
int main()
{
int nod, grad, i, j, a, b, muchii = 0, n, vecin, nou;
fin>>n;
for(i = 1; i <= n; i++){
fin>>a>>b;
iesiri.push(make_pair(a, i));
intrari.push(make_pair(b, i));
}
while(!intrari.empty() && !iesiri.empty()){
nod = iesiri.top().second;
grad = iesiri.top().first;
muchii += grad;
iesiri.pop();
for(i = 0; i < grad; i++){
vecin = intrari.top().second;
nou = intrari.top().first-1;
rem.push(make_pair(nou, vecin));
graf[nod].push_back(intrari.top().second);
intrari.pop();
}
for(i = 0; i < grad; i++){
if(rem.front().first > 0){
intrari.push(rem.front());
}
rem.pop();
}
}
fout<<muchii<<'\n';
for(i = 1; i <= n; i++){
for(j = 0; j < graf[i].size(); j++){
fout<<i<<' '<<graf[i][j]<<'\n';
}
}
return 0;
}