Pagini recente » Cod sursa (job #1450206) | Cod sursa (job #725411) | Cod sursa (job #417282) | Cod sursa (job #362156) | Cod sursa (job #670133)
Cod sursa(job #670133)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxN 505
int N;
int A[maxN], B[maxN];
int ST[maxN], DR[maxN];
bool viz[maxN], M[maxN][maxN];
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;
while (ok)
{
ok = false;
memset (viz, 0, sizeof (viz));
for (int i = 1; i <= A[0]; ++ i)
if (! ST[i] && cupleaza (i)) 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;
}