Pagini recente » Cod sursa (job #2161733) | Cod sursa (job #1766710) | Cod sursa (job #813451) | Cod sursa (job #1200815) | Cod sursa (job #205450)
Cod sursa(job #205450)
#include<stdio.h>
#define DIM 300
#define min(x,y) ((x)<(y)?(x):(y))
FILE *f=fopen("harta.in","r"), *g=fopen("harta.out","w");
int n,x,y,a,nr,lg;
int cap[DIM][DIM],
fl[DIM][DIM],
mat[DIM],
viz[DIM],
mat1[DIM];
void read(){
fscanf(f,"%d",&n);
int i,j;
for(i=1;i<=n;i++) {
fscanf(f,"%d %d",&x,&y);
cap[1][i+1]=x;
cap[n+i+1][n+n+2]=y;
}
for(i=2;i<=n+1;i++)
for(j=n+2;j<=2*n+1;j++)
if((i+n)!=j)
cap[i][j]=1;
fclose(f);
}
int run(){
int p,u,x,i;
mat[0]=1;
p=u=0;
viz[1]=1;
while((p<=u) && !viz[2*n+2]){
x=mat[p++];
for(i=1;i<=2*n+2;i++)
if(!viz[i])
if(fl[x][i]<cap[x][i]) { viz[i]=x; mat[++u]=i;}
}
return !viz[2*n+2];
}
void solve(){
int i;
do{
for(i=1;i<=2*n+2;i++) viz[i]=0;
if(run()) return;
mat1[0]=2*n+2;
lg=0;
a=10000;
while(mat1[lg]!=1){
lg++;
mat1[lg]=viz[mat1[lg-1]];
a=min(a,cap[mat1[lg]][mat1[lg-1]]-fl[mat1[lg]][mat1[lg-1]]);
}
for(i=lg;i>0;i--) {
fl[mat1[i]][mat1[i-1]]+=a;
fl[mat1[i-1]][mat1[i]]-=a;
}
}while(1);
}
void write(){
int i,j;
for(i=2;i<=n+1;i++)
for(j=2+n;j<=2*n+1;j++)
if(fl[i][j]) nr++;
fprintf(g,"%d\n",nr);
for(i=2;i<=n+1;i++)
for(j=2+n;j<=2*n+1;j++)
if(fl[i][j])
fprintf(g,"%d %d\n",i-1,j-n-1);
fclose(g);
}
int main(){
read();
solve();
write();
return 0;
}