Cod sursa(job #5019)

Utilizator nemesisIchim Alexandru Eugen nemesis Data 9 ianuarie 2007 19:21:18
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 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;
}