Cod sursa(job #293768)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 2 aprilie 2009 02:19:58
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<stdio.h>
#include<string.h>
FILE*fin=fopen("harta.in","r");
FILE*fout=fopen("harta.out","w");
#define nm 300
#define min(a,b)((a)<(b)?(a):(b))
#define infi 2000000000
int n,flow[nm][nm],cap[nm][nm],tata[nm],viz[nm],coada[nm];
struct nod
{
  int inf;
  nod *urm;
};
nod *g[nm];
int bfs()
{
  int i,nd,nnd;
  nod *q;  
  memset(viz,0,sizeof(viz));  
  coada[0]=1;
  coada[1]=1;
  viz[1]=1;
  for(i=1;i<=coada[0];i++)
  {
    nd=coada[i];
    q=g[nd];
    while(q)
    {
      nnd=q->inf;
      if(!viz[nnd]&&(cap[nd][nnd]-flow[nd][nnd]))
      {
        coada[0]++;
        coada[coada[0]]=nnd;
        viz[nnd]=1;
        tata[nnd]=nd;
        if(nnd==2*n+2) return 1;
      }      
      q=q->urm;
    }
  }
  return 0;
}
inline void add(int a,int b)
{
  nod *q=new nod;
  q->inf=b;
  q->urm=g[a];
  g[a]=q;
}
int main()
{
  int i,j,flux=0,flux_crt,nd,a,b;  
  tata[1]=0;
  memset(cap,0,sizeof(cap));
  memset(flow,0,sizeof(flow));
  fscanf(fin,"%d",&n);
  for(i=1;i<=2*n+2;i++)
    g[i]=NULL;
  for(i=1;i<=n;i++)
  {
    fscanf(fin,"%d%d",&a,&b);
    cap[1][i+1]=a;
    cap[i+n+1][2*n+2]=b;
    add(1,i+1);
    add(i+1,1);
    add(i+n+1,2*n+2);
    add(2*n+2,i+n+1);
  }
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      if(i!=j)
      {
        cap[i+1][j+n+1]=1;
        add(i+1,j+n+1);
        add(j+n+1,i+1); 
      }  
  while(bfs())
  {
    flux_crt=infi;
    nd=2*n+2;
    while(tata[nd])
    {
      flux_crt=min(flux_crt,cap[tata[nd]][nd]-flow[tata[nd]][nd]);             
      nd=tata[nd];
    }
    flux+=flux_crt;
    nd=2*n+2;
    while(tata[nd])
    {
      flow[tata[nd]][nd]+=flux_crt;
      flow[nd][tata[nd]]-=flux_crt;
      nd=tata[nd];
    }
  }
  fprintf(fout,"%d\n",flux);
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      if(i!=j) if(flow[i+1][j+n+1]==1) fprintf(fout,"%d %d\n",i,j);
  fclose(fin);
  fclose(fout);
  return 0;
}