Pagini recente » Cod sursa (job #2111067) | Cod sursa (job #654279) | Cod sursa (job #2789374) | Cod sursa (job #2163970) | Cod sursa (job #670119)
Cod sursa(job #670119)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define maxN 105
int ST[maxN][maxN], DR[maxN][maxN];
bool A[maxN][maxN], N;
int in[maxN], out[maxN];
int viz[maxN];
bool cuplaj (int x, int poz)
{
if (viz[x] >= in[x]) return false;
viz[x] ++;
for (int i = 1; i <= N; ++ i)
{
if (i == x) continue;
if (A[x][i]) continue;
if (DR[i][0] < out[i])
{
DR[i][0] ++;
DR[i][DR[i][0]] = x;
if (ST[x][0] < poz)
{
ST[x][0] ++;
ST[x][ST[x][0]] = i;
}
else ST[x][poz] = i;
A[x][i] = true;
return true;
}
else
for (int j = 1; j <= DR[i][0]; ++ j)
{
int q = 0;
for (int t = 1; t <= ST[DR[i][j]][0]; ++ t)
if (ST[DR[i][j]][t] == i)
{
q = t;
break;
}
if (cuplaj (DR[i][j], q))
{
A[DR[i][j]][i] = false;
DR[i][j] = x;
if (ST[x][0] < poz)
{
ST[x][0] ++;
ST[x][ST[x][0]] = i;
}
else ST[x][poz] = i;
A[x][i] = true;
return true;
}
}
}
return false;
}
int main()
{
freopen ("harta.in", "r", stdin);
freopen ("harta.out", "w", stdout);
scanf ("%d", &N);
int S = 0;
for (int i = 1; i <= N; ++ i)
{
scanf ("%d %d", &in[i], &out[i]);
S += in[i];
}
bool ok = true;
while (ok)
{
ok = false;
memset (viz, 0, sizeof (viz));
for (int i = 1; i <= N; ++ i)
if (ST[i][0] < in[i] && cuplaj (i, ST[i][0] + 1)) ok = true;
}
printf ("%d\n", S);
for (int i = 1; i <= N; ++ i)
for (int j = 1; j <= ST[i][0]; ++ j) printf ("%d %d\n", i, ST[i][j]);
return 0;
}