Cod sursa(job #3193552)

Utilizator alexnohai04Nohai Alexandru alexnohai04 Data 14 ianuarie 2024 21:26:52
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");
const int MaxN = 205;
int nrOr, nrDr, srs, dest, flow[MaxN][MaxN], cap[MaxN][MaxN] , from[MaxN];


bool bfs()
{
    queue<int> q;
  
    vector<bool> viz(MaxN, false);

    q.push(srs);
    viz[srs] = true;

    while (!q.empty() && !viz[dest])
    {
        int nod = q.front();
        for (int vec = 1; vec <= dest; ++vec)
            if (vec != nod && !viz[vec] && flow[nod][vec] < cap[nod][vec])
            {
                from[vec] = nod;
                viz[vec] = true;
                q.push(vec);
            }
        q.pop();
    }
    return viz[dest];
}

int main()
{
    f >> nrOr;
    srs = 2 * nrOr + 3;
    dest = 2 * nrOr + 2;

    for (int i = 1; i <= nrOr; ++i)
        for (int j = i + 1; j <= nrOr; ++j)
        {
            cap[2 * i][2 * j + 1] = cap[2 * j][2 * i + 1] = 1;
        }

    for (int i = 1; i <= nrOr; ++i)
    {
        int a, b;
        f >> a >> b;
        nrDr += a;
        cap[2 * i + 1][dest] = b;
        cap[srs][2 * i] = a;
    }
    // Aplicarea algoritmului Edmonds-Karp pt fluxul maxim
    while (bfs())
    {
        for (int i = 1; i <= srs; ++i)
            if (from[i] && flow[i][dest] < cap[i][dest])
            {
                from[dest] = i;
                int node = dest, mini = 10000;

                while (from[node])
                {
                    mini = min(mini, cap[from[node]][node] - flow[from[node]][node]);
                    node = from[node];
                }

                node = dest;

                while (from[node])
                {
                    flow[from[node]][node] += mini;
                    flow[node][from[node]] -= mini;
                    node = from[node];
                }
            }
    }

    g << nrDr << '\n';
    for (int i = 1; i < dest; ++i)
        for (int j = 1; j < dest; ++j)
            if (flow[i][j] > 0)
                cout << i/2 << ' ' << j/2 << '\n';

    return 0;
}