Pagini recente » Cod sursa (job #449770) | Cod sursa (job #1650458) | Cod sursa (job #1061109) | Cod sursa (job #1916197) | Cod sursa (job #670144)
Cod sursa(job #670144)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxN 10010
#define maxNN 110
int N;
int A[maxN], B[maxN];
int ST[maxN], DR[maxN];
bool viz[maxN], M[maxNN][maxNN];
bool cupleaza (int nod)
{
if (viz[nod]) return false;
viz[nod] = true;
for (int i = 1; i <= B[0]; ++ i)
{
if (A[nod] == B[i]) continue;
if (M[A[nod]][B[i]]) continue;
if (! DR[i] || cupleaza (DR[i]))
{
if (DR[i]) M[A[DR[i]]][B[i]] = false;
ST[nod] = i;
DR[i] = nod;
M[A[nod]][B[i]] = true;
return true;
}
}
return false;
}
int main()
{
freopen ("harta.in", "r", stdin);
freopen ("harta.out", "w", stdout);
scanf ("%d", &N);
for (int i = 1; i <= N; ++ i)
{
int in, out;
scanf ("%d %d", &in, &out);
for (int t = 1; t <= in; ++ t) A[++ A[0]] = i;
for (int t = 1; t <= out; ++ t) B[++ B[0]] = i;
}
bool ok = true;
int cuplaj = 0;
while (cuplaj < A[0])
{
ok = false;
memset (viz, 0, sizeof (viz));
for (int i = 1; i <= A[0]; ++ i)
if (! ST[i] && cupleaza (i)) ++ cuplaj, ok = true;
}
printf ("%d\n", A[0]);
for (int i = 1; i <= A[0]; ++ i)
if (ST[i]) printf ("%d %d\n", A[i], B[ST[i]]);
return 0;
}