Pagini recente » Cod sursa (job #2793345) | Cod sursa (job #1269864) | Cod sursa (job #1269259) | Cod sursa (job #1296068) | Cod sursa (job #1444233)
#include <cstdio>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
#define Nmax 205
int graf[Nmax][Nmax];
int gri[Nmax], gre[Nmax]; // graf interior, grad exterior
int f[Nmax][Nmax], c[Nmax][Nmax], t[Nmax]; // flux, capacitate, tati
int n, flow, s, d;
queue <int> q;
void read(){
scanf("%i", &n);
for(int i = 1; i <= n; ++i)
scanf("%i %i", &gre[i], &gri[i]);
fclose(stdin);
}
int bfs(){
int u;
q.push(0);
memset(t, -1, sizeof(t));
while(!q.empty()){
u = q.front();
q.pop();
if(u == d){
while(!q.empty()) q.pop();
return t[d];
}
for(int v = 0; v <= d; ++v)
if(graf[u][v])
if( (t[v] == -1) && (c[u][v] != f[u][v]) ){
t[v] = u;
q.push(v);
}
}
return t[d];
}
void max_Flow(){
int r;
while(bfs() != -1){
for(int v = n+1; v <= d-1; ++v)
if( (t[v] != -1) && (c[v][d] != f[v][d] )){
r = c[v][d] - f[v][d];
for(int j = v; j != 0; j = t[j])
r = min(r, c[t[j]][j] - f[t[j]][j]);
if(r > 0){
f[v][d] += r;
f[d][v] -= r;
for(int j = v; j != 0; j = t[j]){
f[t[j]][j] += r;
f[j][t[j]] -= r;
}
flow += r;
}
}
}
}
void solve(){
// contruesc graful bipartit si adaug un nod sursa si un nod destinatie
for(int i = 1; i <= n; ++i)
for(int j = n+1; j <= 2*n; ++j){
graf[i][j] = graf[j][i] = 1;
c[i][j] = 1;
}
s = 0; d = 2*n+1;
for(int i = 1; i <= n; ++i) graf[i][n+i] = 0;
for(int i = 1; i <= n; ++i){
graf[s][i] = graf[i][s] = 1;
c[s][i] = gre[i];
graf[n+i][d] = graf[d][n+i] = 1;
c[n+i][d] = gri[i];
}
max_Flow();
}
void write(){
printf("%i\n", flow);
for(int i = 1; i <= n; ++i)
for(int j = n+1; j <= 2*n; ++j)
if(f[i][j]) printf("%i %i\n", i, j-n);
}
int main(){
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
read();
solve();
write();
}