Cod sursa(job #19598)

Utilizator vlad_popaVlad Popa vlad_popa Data 19 februarie 2007 19:44:33
Problema Taramul Nicaieri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
using namespace std;

#include <cstdio>

#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;
}

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

void ford_fulk (int s, int t)
{
  int min, i;
  //++ iter;
  do
   {
     min = INF;
     bf ();
     if (!d[t])
       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;
   }
  while (d[t]);
}

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

  scanf ("%d", &N);
  for (int 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 (int i = 2; i <= N + 1; ++ i)
    for (int 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 (int i = 2; i <= N + 1; ++ i)
    for (int j = N + 2; j <= 2*N + 1; ++ j)
      if (f[i][j] > 0)
        printf ("%d %d\n", i - 1, j - N - 1);
  return 0;
}