Cod sursa(job #2961594)

Utilizator 4N70N1U5Antonio Nitoi 4N70N1U5 Data 6 ianuarie 2023 19:01:31
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.16 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int cap[202][202], n, max_flow, current_flow;
vector<int> vis, pred;
vector<vector<int>> adj;

// Parcurg graful prin BFS, cu conditia ca fluxul exuistent dintre
// doua noduri sa nu depaseasca capacitatea muchiei respective.
// De asemenea, pe langa faptul ca un anume nod este vizitat, retin
// si care este nodul din care am ajuns in acesta (predecesorul).
bool bfs()
{
    fill(vis.begin(), vis.end(), 0);
    fill(pred.begin(), pred.end(), 0);

    vis[0] = 1;
    pred[0] = 0;

    queue<int> q;
    q.push(0);

    while (!q.empty())
    {
        int c = q.front();

        q.pop();

        // Am ajuns in nodul destinatie.
        if (c == 2 * n + 1)
            return true;

        for (int i = 0; i < adj[c].size(); i++)
        {
            if (!vis[adj[c][i]] && 0 < cap[c][adj[c][i]])
            {
                q.push(adj[c][i]);
                pred[adj[c][i]] = c;
                vis[adj[c][i]] = 1;
            }
        }
    }
    
    return false;
}

int main()
{
    fin >> n;

    // Fiecare nod din graf are doua copii, una in multimea L si una
    // in multimea R.
    // Nodurile din multimea L sunt numerotate de la 1 la n, iar cele
    // din multimea R de la n + 1 la 2 * n.
    vis.resize(2 * n + 2);
    pred.resize(2 * n + 2);
    adj.resize(2 * n + 2);

    // Adaug pe 0 ca nod sursa si muchii intre acesta si toate nodurile
    // din multimea L cu capacitatile egale cu gradele de iesire.
    // Adaug pe 2 * n + 1 ca nod destinatie si muchii intre acesta si
    // toate nodurile din multimea R cu capacitatile egale cu gradele
    // de intrare.
    // Adaug muchii intre nodurile din multimea L si R, dar nu de la
    // un nod la el insusi.
    for (int i = 1; i <= n; i++)
    {
        adj[0].push_back(i);
        adj[i].push_back(0);

        adj[i + n].push_back(2 * n + 1);
        adj[2 * n + 1].push_back(i + n);

        for (int j = n + 1; j <= 2 * n; j++)
        {
            if (i != j - n)
            {
                adj[i].push_back(j);
                adj[j].push_back(i);

                cap[i][j] = 1;
            }
        }

        int x, y;
        fin >> x >> y;

        cap[0][i] = x;
        cap[i + n][2 * n + 1] = y;
    }

    // Cat timp exista un drum intre sursa si destinatie.
    while (bfs())
    {
        // Iterez prin vecinii nodului destinatie.
        for (int i = 0; i < adj[2 * n + 1].size(); i++)
        {
            // Daca un nod vecin cu nodul destinatie este vizitat,
            // inseamna ca acesta este unul dintre predecesorii nodului
            // destinatie. In acest caz, exista un drum intre sursa
            // si destinatie prin acest nod.
            if (vis[adj[2 * n + 1][i]])
            {
                pred[2 * n + 1] = adj[2 * n + 1][i];
                
                current_flow = __INT_MAX__;

                // Determin care este limitarea de pe ruta
                // (muchia cu capacitate minima).
                for (int j = 2 * n + 1; j != 0; j = pred[j])
                {
                    current_flow = min(current_flow, cap[pred[j]][j]);
                }

                // Adun fluxul curent la fluxul de pe fiecare muchie
                // din lant si il scad pentru a obtine flux negativ
                // pe muchiile de intoarcere.
                for (int j = 2 * n + 1; j != 0; j = pred[j])
                {
                    cap[pred[j]][j] -= current_flow;
                    cap[j][pred[j]] += current_flow;
                }

                // Adun fluxul curent la fluxul maxim.
                max_flow += current_flow;
            }
        }
    }

    // Valoarea fluxului maxim coincide cu numarul de drumuri construite.
    fout << max_flow << '\n';

    // Afisez nodurile intre care exista o muchie saturata.
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < adj[i].size(); j++)
            if (!cap[i][adj[i][j]])
                fout << i << ' ' << adj[i][j] - n << '\n';

    return 0;
}