Pagini recente » Colors | Cod sursa (job #2024879) | Cod sursa (job #2688068) | Profil Alexbiraianu | Cod sursa (job #17720)
Cod sursa(job #17720)
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;
}