Pagini recente » Cod sursa (job #2904616) | Cod sursa (job #1640335) | Cod sursa (job #672372) | Cod sursa (job #1313766) | Cod sursa (job #1397971)
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
#define MAXN 120
using namespace std;
const int off = 110, start = 105, fin = 106;
int n, cap[2 * MAXN][2 * MAXN], fx[2 * MAXN][2 * MAXN];
int bk[2 * MAXN], x, totfx;
vector<int> G[MAXN];
bool BFS(){
queue<int> q;
int x;
memset(bk, 0, sizeof(bk));
q.push(start);
while(!q.empty()){
x = q.front(); q.pop();
for(auto y: G[x])
if(!bk[y] && fx[x][y] < cap[x][y]){
bk[y] = x;
q.push(y);
}
}
return bk[fin] != 0;
}
int main(){
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
int i, j;
scanf("%d", &n);
for(i = 1; i <= n; i++){
scanf("%d %d", &cap[start][i], &cap[i + off][fin]);
G[start].push_back(i);
G[i + off].push_back(fin);
}
for(i = 1; i <= n; i++)
for(j = off + 1; j <= off + n; j++)
if(i + off != j){
cap[i][j] = 1;
G[i].push_back(j);
G[j].push_back(i);
}
while(BFS()){
for(i = off + 1; i <= off + n; i++)
if(fx[i][fin] < cap[i][fin]){
x = i;
while(bk[x]){
if(fx[bk[x]][x] == cap[bk[x]][x]) break;
x = bk[x];
}
if(bk[x]) continue;
x = i;
fx[x][fin]++;
fx[fin][x]--;
totfx++;
while(bk[x]){
fx[bk[x]][x]++;
fx[x][bk[x]]--;
x = bk[x];
}
}
}
printf("%d\n", totfx);
for(i = 1; i <= n; i++)
for(j = off + 1; j <= off + n; j++)
if(fx[i][j])
printf("%d %d\n", i, j - off);
return 0;
}