Pagini recente » Cod sursa (job #1401427) | Cod sursa (job #2514637) | Cod sursa (job #86374) | Cod sursa (job #1507699) | Cod sursa (job #1163327)
#include <cstdio>
#include <vector>
#define nmax 105
#define boolMax(a,b) (a)?(true):(b)
using namespace std;
vector <int> g[nmax];
int n,sum;
int input[nmax],output[nmax];
bool existent(int a,int b) {
for (vector <int> :: iterator it = g[a].begin();it != g[a].end();it++) {
if (*it == b) return true;
}
return false;
}
bool link(int x) {
for (int i=1;i<=n;i++) {
if (i == x) continue;
if (input[i] > 0 && !existent(x,i)) {
input[i]--;
output[x]--;
g[x].push_back(i);
return true;
}
}
return false;
}
bool insert(int x) {
for (int i=1;i <= n;i++) {
if (i == x) continue;
for (vector <int> :: iterator it = g[i].begin();it != g[i].end();it++) {
if (*it == x) continue;
if (existent(i,x) || existent(x,*it)) continue;
int ct = *it;
g[i].erase(it);
g[i].push_back(x);
g[x].push_back(ct);
input[x]--,output[x]--;
return true;
}
}
return false;
}
int main() {
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d %d",&output[i],&input[i]);
sum += output[i];
}
for (bool changed = true;changed;) {
changed = false;
for (int i=1;i<=n;i++) {
if (output[i] > input[i]) changed = boolMax(link(i),changed);
else if (output[i] > 0 && input[i] > 0) changed = boolMax(insert(i),changed);
}
}
printf("%d\n",sum);
for (int i=1;i<=n;i++) {
for (vector <int> :: iterator it = g[i].begin();it != g[i].end();it++) {
printf("%d %d\n",i,*it);
}
}
return 0;
}