Cod sursa(job #17720)

Utilizator vlad_popaVlad Popa vlad_popa Data 16 februarie 2007 19:02:10
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
using namespace std;

#include <cstdio>
#include <algorithm>

#define FIN "harta.in"
#define FOUT "harta.out"
#define NMAX 101

int N, st[NMAX*NMAX], dr[NMAX*NMAX], d[NMAX*NMAX], iter, viz[NMAX*NMAX], sol;
int a[NMAX][NMAX];
struct nod {int go, come;};
nod v[NMAX];
bool con[NMAX*NMAX];

int df (int s)
{
  if (viz[s] == iter)
    return 0;
  viz[s] = iter;

  for (int i = 1; i <= sol; ++ i)
    if (st[s] != dr[i] && !a[st[s]][dr[i]])
      if (d[i] == -1)
       {
         d[i] = s;
         a[st[s]][dr[i]] = 1;
         return 1;
       }
      else
       {
         int rez = df (d[i]);
         if (rez == 1)
          {
            a[st[d[i]]][dr[i]] = 0;
            d[i] = s;
            a[st[s]][dr[i]] = 1;
            return 1;
          }
       }
  return 0;
}

int
 main ()
{
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  scanf ("%d", &N);
  for (int i = 1; i <= N; ++ i)
   {
     scanf ("%d%d", &v[i].go, &v[i].come);
     sol += v[i].go;
   }
  int k = 1;
  for (int i = 1; i <= sol; ++ i)
    if (v[k].go)
     {
       -- v[k].go;
       st[i] = k;
     }
    else
     {
       while (!v[k].go)
         ++ k;
       st[i] = k;
       -- v[k].go;
     }
  k = 1;
  for (int i = 1; i <= sol; ++ i)
    if (v[k].come)
     {
       -- v[k].come;
       dr[i] = k;
     }
    else
     {
       while (!v[k].come)
         ++ k;
       dr[i] = k;
       -- v[k].come;
     }
  for (int i = 1; i <= sol; ++ i)
    d[i] = -1;
  bool verif = false;
  while (!verif)
   {
     verif = true;
     for (int i = 1; i <= sol; ++ i)
       if (!con[i])
        {
          ++ iter;
          df (i);
          con[i] = true;
          verif = false;
        }
   }
  printf ("%d\n", sol);
  for (int i = 1; i <= sol; ++ i)
    printf ("%d %d\n", st[d[i]], dr[i]);
  return 0;
}