Pagini recente » Cod sursa (job #1619084) | Cod sursa (job #1915852) | Cod sursa (job #1896690) | Cod sursa (job #2817749) | Cod sursa (job #222857)
Cod sursa(job #222857)
#include<stdio.h>
#define N 210
int nr[N],f[N][N],c[N][N],t[N],n,s;
bool bf()
{
int x,y,p=0,u=0,coada[N];
bool viz[N]={false};
coada[u++]=0;
viz[0]=true;
while(p!=u)
{
x=coada[p++];
for(y=1 ; y<=2*n+1 ; ++y)
if(c[x][y]>f[x][y] && viz[y]==false)
{
coada[u++]=y;
viz[y]=true;
t[y]=x;
if(y==2*n+1)
return true;
}
}
return false;
}
void actualizare()
{
int x=2*n+1;
while(x)
{
++f[t[x]][x];
--f[x][t[x]];
x=t[x];
}
}
void flux(){
while(bf())
{
//m=minim();
actualizare();
}
}
void prelucrare(){
int i,j;
printf("%d\n",s);
for(i=1;i<=n;++i){
for(j=n+1;j<=n<<1;++j)
if(f[i][j])
printf("%d %d\n",i,j-n);
}
}
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",&nr[i],&nr[i+n]);
c[0][i]=nr[i];
c[i+n][2*n+1]=nr[i+n];
s+=nr[i];
}
for(i=1;i<=n;++i)
for(j=n+1;j<=2*n;++j)
if(j-i!=n)
c[i][j]=1;
flux();
prelucrare();
fclose(stdin);
fclose(stdout);
return 0;
}