Cod sursa(job #299928)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 7 aprilie 2009 09:35:42
Problema Taramul Nicaieri Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>
#define N 105

using namespace std;

int flux[N<<1][N<<1];
int inc,sf,n,m,S,D;
int Q[N],tati[N];
int pl[N],in[N],numar;

void citire()
{
     freopen ("harta.in","r",stdin);
     freopen ("harta.out","w",stdout);
     scanf ("%d",&n);
     for (int i=1;i<=n;i++)
          scanf ("%d %d",&pl[i],&in[i]);
     S=0;
     D=2*n+1;
}

void init()
{
     for (int i=1;i<=n;i++)
          flux[S][i]=pl[i];

     for (int i=1;i<=n;i++)
          flux[i+n][D]=in[i];

     for (int i=1;i<=n;i++)
          for (int j=n+1;j<=n<<1;j++)
               if (i!=j-n)
                    flux[i][j]=1;
}

int bell()
{
     int n1;
     for (int i=1;i<=(n<<1)+1;i++)
          tati[i]=-1;
     inc=0;
     sf=1;
     Q[0]=S;
     tati[S]=0;
     while (inc<sf)
     {
          n1=Q[inc++];
          for (int i=1;i<=D;i++)
               if (flux[n1][i] && tati[i]==-1)
               {
                    tati[i]=n1;
                    Q[sf++]=i;
               }
          if (tati[D]!=-1)
               return 1;
     }
     return 0;
}

void fl()
{
     int poz;
     while (bell())
     {
          poz=D;
          while (poz!=S)
          {
               flux[tati[poz]][poz]--;
               flux[poz][tati[poz]]++;
               poz=tati[poz];
          }
          numar++;
     }
}

void afish()
{
     printf("%d\n",numar);
     for (int i=1;i<=n;i++)
          for (int j=n+1;j<=n<<1;j++)
               if (!flux[i][j] && i!=j-n)
                    printf("%d %d\n",i,j-n);
}

int main ()
{
     citire();
     init();
     fl();
     afish();
     return 0;
}