Pagini recente » Cod sursa (job #1848002) | Cod sursa (job #1707158) | Cod sursa (job #885702) | Cod sursa (job #126800) | Cod sursa (job #1589202)
#include<cstdio>
#include<bitset>
#include<queue>
#define N 200
using namespace std;
int c[N+3][N+3];
int f[N+3][N+3];
int tata[N+3];
bitset<N+3> viz;
int m;
int minim(int a,int b){
return (a<b) ? a : b;
}
bool bfs(){
int nod,i;
queue<int> q;
viz.reset();
q.push(1);
viz[1]=true;
while(!q.empty()){
nod=q.front();
q.pop();
if (nod==m) break ;
for(i=2;i<=m;i++)
if (c[nod][i]-f[nod][i]>0 &&viz[i]==false){
tata[i]=nod;
viz[i]=true;
q.push(i);
}
}
return viz[m];
}
void flux(){
int i,min,nod;
while(bfs()){
for(i=1;i<m;i++)
if (c[i][m]-f[i][m]>0 &&viz[i]==true){
tata[m]=i;
min=c[i][m]-f[i][m];
nod=i;
while(nod!=1){
min=minim(min,c[tata[nod]][nod]-f[tata[nod]][nod]);
nod=tata[nod];
}
nod=m;
while(nod!=1){
f[tata[nod]][nod]+=min;
f[nod][tata[nod]]-=min;
nod=tata[nod];
}
}
}
}
int main(){
freopen ("harta.in","r",stdin);
freopen ("harta.out","w",stdout);
int n,i,x,y,j,s=0;
scanf ("%d",&n);
m=n*2+2;
for(i=1;i<=n;i++){
scanf ("%d%d",&x,&y);
c[1][i+1]=x;
c[n+i+1][m]=y;
s+=x;
}
for(i=2;i<=n+1;i++){
for(j=n+2;j<m;j++)
c[i][j]=1;
c[i][n+i]=0;
}
flux();
printf ("%d\n",s);
for(i=2;i<=n+1;i++)
for(j=n+2;j<m;j++)
if (f[i][j]==1) printf ("%d %d\n",i-1,j-n-1);
return 0;
}