Cod sursa(job #20099)

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

#include <cstdio>
#include <vector>

#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];
vector <int> coada;

void bf ()
{
  int v, i;
  vector <int> :: iterator it;
  d[1] = iter;
  coada.push_back (1);
  while (!coada.empty())
   {
     it = coada.end() - 1;
     v = *it;
     coada.pop_back();
     for (i = 1; i <= 2*N + 2; ++ i)
       if (c[v][i] > f[v][i] && d[i] != iter)
        {
          d[i] = iter;
          pred[i] = v;
          coada.push_back (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;
  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])
        printf ("%d %d\n", i - 1, j - N - 1);
  return 0;
}