Pagini recente » Cod sursa (job #1594532) | Cod sursa (job #1753491) | Cod sursa (job #1305666) | Cod sursa (job #547664) | Cod sursa (job #2589749)
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 997
using namespace std;
const int NMAX = 105;
int N, ans;
int capInput[NMAX], capOutput[NMAX];
int Left[NMAX][NMAX];
bool seen[NMAX];
vector <int> edges[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]);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++){
if(i == j) continue;
edges[i].push_back(j);
}
}
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 <= Left[node][0]; j++)
if(Left[node][j] == i){
ok = false;
break;
}
if(ok){
if(Right[i][0].first < capOutput[i]){
Right[i][Right[i][0].first + 1] = {node, pos};
Right[i][0].first++;
Left[node][pos] = i;
Left[node][0] = max(pos, Left[node][0]);
return true;
}
}
}
for(int i = 1; i <= N; i++){
if(i == node) continue;
bool ok = true;
for(int j = 1; j <= Left[node][0]; j++)
if(Left[node][j] == i){
ok = false;
break;
}
if(ok)
for(int j = 1; j <= Right[i][0].first; i++)
if(cuplaj(Right[i][j].first, Right[i][j].second)){
Right[i][j] = {node, pos};
Left[node][pos] = i;
Left[node][0] = max(pos, Left[node][0]);
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(Left[i][0] < capInput[i])
retry |= cuplaj(i, Left[i][0] + 1);
}
for(int i = 1; i <= N; i++)
ans += Left[i][0];
printf("%d\n", ans);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= Left[i][0]; j++)
printf("%d %d\n", i, Left[i][j]);
return 0;
}