Cod sursa(job #164206)

Utilizator FlorinC1996Florin C FlorinC1996 Data 23 martie 2008 17:47:48
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
 #include<stdio.h>   
#include<string.h>   
  
int n, c[304][304], out[101], in[101], f[304][304];   
  
  
void afis()   
{   
  int sum=0;   
  for(int i=1; i<=n; ++i) sum+= in[i]+out[i];   
  printf("%d\n",sum/2);   
  for(int i=0; i<=2*n+1; ++i) {   
    for(int j=0; j<=2*n+1; ++j) if(f[i][j]>0 && i!=0 && j!=2*n+1) printf("%d %d\n",(i+1)/2,j/2);   
 }   
}   
  
void init()   
{   
  for(int i=1; i<=n; ++i) {   
    c[0][2*i-1] = out[i];   
    c[2*i][2*n+1] = in[i];   
    for(int j=1; j<=n; ++j) if(i!=j) c[2*i-1][2*j]= 1;   
  }   
}   
  
int BFS()   
{   
  int Q[1000], p=1, q=1, pred[303], viz[303];   
  memset(viz, 0, sizeof(viz));   
  memset(pred,-1, sizeof(pred));   
  memset(Q,0,sizeof(Q));   
  p=1;   
  q=1;   
  Q[1]= 0;   
  viz[0]=1;   
  while(p<=q) {   
    for(int i=1; i<= 2*n+1; ++i) if(!viz[i] && c[Q[p]][i]- f[Q[p]][i] > 0 ) {   
      Q[++q]= i;   
      pred[i]= Q[p];         
      viz[i]= 1;   
    }   
    p++;   
  }   
  
  if(!viz[2*n+1]) return 0;   
  
  int min=1;   
  p= 2*n+1;   
  while(p) {   
    f[pred[p]][p]+=min;   
    f[p][pred[p]]-=min;   
    p=pred[p];   
  }   
  
  return 1;   
}   
  
int main()   
{   
  freopen("harta.in","r",stdin);   
  scanf("%d",&n);   
  for(int i=1; i<=n; ++i) scanf("%d %d",&out[i], &in[i]);   
  init();   
     
  freopen("harta.out","w",stdout);   
  while(BFS()) ;   
  afis();   
  
  return 0;   
}