Cod sursa(job #2961555)

Utilizator TindecheTindeche Alexandru Tindeche Data 6 ianuarie 2023 17:49:24
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <stack>
#include <unordered_map>

using namespace std;

// ifstream fin("input.txt");
// ofstream fout("output.txt");

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


/*
 * Algotitm:
 * - Se adauga un nou nod sursa si un nou nod destinatie (cu muchii care au costul egal cu gradul de intrare respectiv iesire)
 * - Numarul de noduri se dubleaza si se pun in doua multimi distincte
 * - Cele doua multimi se leaga intre ele prin muchii de cost 1 cu o conditie:
 *     - daca cele doua multimi sunt denumite X si Y, atunci va exista o muchie de la Xi la Yj daca i != j
 * - Se aplica algoritmul lui Ford-Fulkerson pe graful rezultat
 * - Muchiile saturate ne dau muchiile care fac parte din graful initial
 */

// --------------------------------- //
vector<int> tata;
vector<int> vizitat;
int a[300][300];
int intrare[300];
int iesire[300];
int n, m;
int s, d;

// --------------------------------- //

int bfs()
{
    tata.clear();
    tata.resize(2*n+2, 0);
    vizitat.clear();
    vizitat.resize(2*n+2, 0);
    queue <int> q;
    q.push(s);
    vizitat[s] = 1;
    tata[s] = -1;
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();

        if(nod == d)
            return 1;

        for (int i = 1; i <= 2 * n + 1; i++)
        {
            if (!vizitat[i] && a[nod][i] > 0)
            {
                q.push(i);
                tata[i] = nod;
                vizitat[i] = 1;
            }
        }
    }
    return 0;
}

int fordFulkerson()
{
    int flux = 0;
    int fluxCurent = 0;
    while (bfs())
    {
        for(int i = 1; i <= n; i++)
        {
            if (vizitat[n + i] && a[n + i][2 * n + 1] > 0)
            {
                fluxCurent = INT_MAX;
                tata[d] = n + i;
                for(int nod = d; nod != s; nod = tata[nod])
                    fluxCurent = min(fluxCurent, a[tata[nod]][nod]);

                if (fluxCurent == 0)
                    continue;

                for (int nod = d; nod != s; nod = tata[nod])
                {
                    a[tata[nod]][nod] -= fluxCurent;
                    a[nod][tata[nod]] += fluxCurent;
                }
                flux += fluxCurent;
            }
        }
    }
    return flux;
}

int main ()
{
    fin >> n;
    s = 0;
    d = 2 * n + 1;
    for(int i = 1; i <= n; i++)
    {
        // Citim datele de intrare
        int x, y;
        fin >> y >> x;
        intrare[i] = x;
        iesire[i] = y;
        a[0][i] = y;
        a[i + n][2 * n + 1] = x;

        for(int j = 1; j <= n; j++)
        {
            if(i != j)
            {
                a[i][j + n] = 1;
            }
        }
    }

    fout << fordFulkerson() << endl;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(a[i][j + n] == 0 && i != j)
            {
                fout << i << " " << j << endl;
            }
        }
    }

    return 0;
}