Cod sursa(job #288261)

Utilizator drag0shSandulescu Dragos drag0sh Data 25 martie 2009 17:45:56
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda aa Marime 0.99 kb
#include <stdio.h>
#include <string.h>
FILE *f=fopen("harta.in","r"),*g=fopen("harta.out","w");

int a[101],b[101],n,gr[100][100],v[100],d[100],s;

void citire(){
  int i;
  fscanf(f,"%d",&n);
  for(i=1;i<=n;i++)
    {fscanf(f,"%d%d",&a[i],&b[i]);s+=a[i];}

}

int pair(int o){
  if(v[o]==1) return 0;
  v[o]=1;
  int x,i;
  
  for(x=1;x<=n&&a[o]>0;x++)
    if(b[x]>0&&!gr[x][o]&&!gr[o][x]&&o!=x){
      gr[o][x]=1;
      a[o]--;
      b[x]--;
    }
  if(!a[o])return 1;
  for(x=1;x<=n&&a[o]>0;x++){
    if(!gr[o][x]&&!gr[o][x]&&o!=x){
    for(i=1;i<=n;i++)
      if(gr[x][i]==1){
	a[x]++;
	b[i]++;
	if(pair(i))
	  gr[o][x]=1;
	a[o]--;
	b[x]--;	
      }
    }
  }
  return 0;
  
}


int main(){
  citire();
  int i,j,stare;
  stare=1;
  while(stare){
    memset(v,0,sizeof(v));
    stare=0;   
    for(i=1;i<=n;i++)if(a[i]) stare|=pair(i);
  }
  fprintf(g,"%d\n",s);
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      if(gr[i][j]){ fprintf(g,"%d %d\n",i,j);gr[j][i]=0;}
   
  
  fclose(f);
  fclose(g);
  return 0;
}