Cod sursa(job #70837)

Utilizator moga_florianFlorian MOGA moga_florian Data 7 iulie 2007 20:48:16
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
using namespace std;
#include<fstream>
#include<stdio.h>
#define Nmax 210

int cap[Nmax][Nmax];
int bfs[Nmax],ant[Nmax];
char viz[Nmax];

int main()
{
FILE *fin=fopen("harta.in","r"),
     *fout=fopen("harta.out","w");
     
int N,i,j,sum=0;
fscanf(fin,"%d",&N);

for(i=1;i<=N;i++) 
  {
  fscanf(fin,"%d%d",&cap[i+N][2*N+1], &cap[0][i]);
  sum+=cap[0][i];
  }
  
for(i=1;i<=N;i++)
  for(j=1;j<=N;j++)
    if(i!=j)
       cap[i][j+N]=1;
       
//flux
int li,lf,dest=2*N+1,X,F=0;

while(1)
  {                 
  li=1,lf=0;
  memset(viz,0,sizeof viz);
  
  viz[0]=1;
  for(i=1;i<=N;i++)
     if(cap[0][i]>0)
        {
        bfs[++lf]=i;
        ant[lf]=0;            
        viz[i]=1;
        }
   
  while(li<=lf)
     {
     X=bfs[li];       
     
     if(X<=N)
        {
        for(i=N+1;i<dest;i++)
           if(cap[X][i] >0 && viz[i]==0 )
               {
               viz[i]=1;
               bfs[++lf]=i;
               ant[lf]=li;         
               }     
        }   
     else
        {
        if(cap[X][dest]>0)
             {
             bfs[++lf]=dest;
             ant[lf]=li;
             break;             
             }
        
        for(i=1;i<=N;i++)
            if(cap[X][i]>0 && viz[i]==0)
               {
               viz[i]=1;
               bfs[++lf]=i;
               ant[lf]=li;            
               }            
        }   
     
     li++;
     }    
     
  if(bfs[lf]<dest) break;
     
  i=lf;
  
  while(bfs[i])
     {
     cap [bfs[ant[i]]] [bfs[i]] --;
     cap [bfs[i]] [bfs[ant[i]]] ++;
     
     i=ant[i];
     }        
     
  F++;
  }
  
sum=0;  
fprintf(fout,"%d\n",F);
for(i=1;i<=N;i++)
  for(j=1;j<=N;j++)
     if(cap[i][j+N]==0 && cap[j+N][i]==1)
        {
        fprintf(fout,"%d %d\n",i,j);
        sum++;
        }
        
if(sum!=F) for(;;);
         
fclose(fin);
fclose(fout);
return 0;
}