Pagini recente » Cod sursa (job #220312) | Cod sursa (job #61481) | Cod sursa (job #3283118) | Cod sursa (job #2962306) | Cod sursa (job #3194982)
#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, flag;
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();
flag = 0;
for(i = 0; i < grad; i++){
vecin = intrari.top().second;
nou = intrari.top().first-1;
intrari.pop();
if(vecin == nod){
rem.push(make_pair(nou+1, vecin));
flag = 1;
i--;
}
else{
rem.push(make_pair(nou, vecin));
graf[nod].push_back(intrari.top().second);
}
}
for(i = 0; i < grad+flag; 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;
}