Pagini recente » Cod sursa (job #1006873) | Cod sursa (job #1037984) | Cod sursa (job #1042025) | Cod sursa (job #2688055) | Cod sursa (job #3190007)
#include <iostream>
#include <fstream>
using namespace std;
#define NMAX 250
#define QMAX (1<<8)
ifstream in("harta.in");
ofstream out("harta.out");
int a[NMAX][NMAX], din[NMAX], dout[NMAX], n, drumuri, q[QMAX], pred[NMAX];
int flux()
{
int i, last, first, nod;
for (i = 0; i < NMAX; i++) { //init coada si predecesori
q[i] = 0;
pred[i] = -1;
}
q[0] = 0;
pred[0] = 0;
//bfs gasire drum pt marire flux
for (first = 0, last = 1; first != last; first = (first + 1) & (QMAX - 1)) //ne asig ca first < qmax-1
{
nod = q[first];
for (i = 0; i < 2 * n + 2; i++)
if (a[nod][i] && pred[i] == -1)
{
pred[i] = nod;
q[last] = i;
last = (last + 1) & (QMAX - 1);
if (i == 2 * n + 1)
{
drumuri++;
return 1;
}
}
}
return 0;
}
int main()
{
int i, j, sin = 0, sout = 0;
in >> n;
for (i = 1; i <= n; i++)
{
in >> din[i] >> dout[i];
sin += din[i];
sout += dout[i];
a[0][i] = din[i];
a[i + n][2 * n + 1] = dout[i];
}
//const graf or
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j) a[i][n + j] = 1;
//conditie pt executie flux
if (sin != sout)
{
out << -1;
return 0;
}
while (flux())
{
//actualiz cap arc in f de dr gasit
for (i = 2 * n + 1; i; i = pred[i]) {
a[i][pred[i]]++;
a[pred[i]][i]--;
}
}
if (drumuri < sin)
{
out << -1;
return 0;
}
else
{
out << drumuri << '\n';
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (a[j + n][i])
out << i << " " << j << '\n';
}
return 0;
}