Cod sursa(job #19624)

Utilizator vlad_popaVlad Popa vlad_popa Data 19 februarie 2007 20:01:57
Problema Taramul Nicaieri Scor 95
Compilator c Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>

#define FIN "harta.in"
#define FOUT "harta.out"
#define NMAX 203
#define INF 0x3f3f3f3f

int N, c[NMAX][NMAX], f[NMAX][NMAX], iter, d[NMAX], pred[NMAX];
int begin, ended, coada[NMAX];

void in (int val)
{
  coada[ended] = val;
  ++ ended;
}

int out ()
{
  int temp = coada[begin];
  ++ begin;
  return temp;
}

void bf ()
{
  int v, i;
  d[1] = iter;
  begin = ended = 0;
  in (1);
  while (begin != ended)
   {
     v = out ();
     for (i = 1; i <= 2*N + 2; ++ i)
       if (c[v][i] > f[v][i] && d[i] != iter)
        {
          d[i] = iter;
          pred[i] = v;
          in (i);
        }
   }
}

void ford_fulk (int s, int t)
{
  int min, i;
  ++ iter;
  while (d[t] != iter)
   {
     min = INF;
     bf ();
     if (d[t] != iter)
       break;
     i = t;
     while (pred[i])
      {
        if (min > c[pred[i]][i] - f[pred[i]][i])
          min = c[pred[i]][i] - f[pred[i]][i];
        i = pred[i];
      }
     i = t;
     while (pred[i])
      {
        f[pred[i]][i] += min;
        f[i][pred[i]] -= min;
        i = pred[i];
      }
     ++ iter;
   }
}

int
 main ()
{
  int x, y, rez = 0, i, j;
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  scanf ("%d", &N);
  for (i = 1; i <= N; ++ i)
   {
     scanf ("%d%d", &x, &y);
     rez += x;
     c[1][i+1] = x;
     c[N+i+1][2*N+2] = y;
   }
  for (i = 2; i <= N + 1; ++ i)
    for (j = N + 2; j <= 2*N + 1; ++ j)
      if (i + N != j)
        c[i][j] = 1;
  ford_fulk (1, 2*N + 2);
  printf ("%d\n", rez);
  for (i = 2; i <= N + 1; ++ i)
    for (j = N + 2; j <= 2*N + 1; ++ j)
      if (f[i][j])
        printf ("%d %d\n", i - 1, j - N - 1);
  return 0;
}