Pagini recente » Cod sursa (job #1479342) | Cod sursa (job #1223758) | Cod sursa (job #2107182) | Cod sursa (job #1487694) | Cod sursa (job #2589785)
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 997
using namespace std;
const int NMAX = 105;
int N, ans;
int lgL[NMAX], lgR[NMAX];
int capInput[NMAX], capOutput[NMAX];
int Left[NMAX][NMAX];
bool seen[NMAX];
pair <int, int> Right[NMAX][NMAX];
void read(){
scanf("%d", &N);
for(int i = 1; i <= N; i++){
scanf("%d%d", &capInput[i], &capOutput[i]);
ans += capInput[i];
}
}
bool cuplaj(int node, int pos){
if(seen[node]) return false;
seen[node] = true;
for(int i = 1; i <= N; i++){
if(i == node) continue;
bool ok = true;
for(int j = 1; j <= lgL[node]; j++)
if(Left[node][j] == i){
ok = false;
break;
}
if(ok){
if(lgR[i] < capOutput[i]){
Right[i][lgR[i] + 1] = {node, pos};
lgR[i]++;
Left[node][pos] = i;
lgL[node] = max(pos, lgL[node]);
return true;
}
}
}
for(int i = 1; i <= N; i++){
if(i == node) continue;
bool ok = true;
for(int j = 1; j <= lgL[node]; j++)
if(Left[node][j] == i){
ok = false;
break;
}
if(ok)
for(int j = 1; j <= lgR[i]; i++)
if(cuplaj(Right[i][j].first, Right[i][j].second)){
Right[i][j] = {node, pos};
Left[node][pos] = i;
lgL[node] = max(pos, lgL[node]);
return true;
}
}
}
int main(){
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
read();
bool retry = true;
while(retry){
retry = false;
for(int i = 1; i <= N; i++)
seen[i] = false;
for(int i = 1; i <= N; i++)
if(lgL[i] < capInput[i])
retry |= cuplaj(i, lgL[i] + 1);
}
printf("%d\n", ans);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= lgL[i]; j++)
printf("%d %d\n", i, Left[i][j]);
return 0;
}