Cod sursa(job #205450)

Utilizator marinMari n marin Data 31 august 2008 20:55:50
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#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;
}