Cod sursa(job #3190002)

Utilizator opreaopreacalin@gmail.comCalin Oprea [email protected] Data 6 ianuarie 2024 19:42:30
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 1.87 kb
#include <iostream>
#include <fstream>
using namespace std;
#define NMAX 150
#define QMAX (1<<8)

ifstream in("harta.in");
ofstream out("harta.in");

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;
}