Pagini recente » Cod sursa (job #962322) | Rating Alexandru (Alex2222) | Diferente pentru runda/viata_periculoasa_pe_infoarena intre reviziile 7 si 6 | Cod sursa (job #2396929) | Cod sursa (job #232498)
Cod sursa(job #232498)
#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())
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;
}