Cod sursa(job #2961880)

Utilizator urluconceptualCiocan Alexandra-Diana urluconceptual Data 7 ianuarie 2023 12:02:54
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <fstream>
#include <vector>
#include <queue>
#define INT_MAX 2147483647;

using namespace std;

//3. 

int n, m, maxFlow, start, final;
vector<vector<int>> rez;
vector<int> anc, gradExt, gradInt;
vector<bool> viz;

//parcurgerea bfs care gaseste lanturi de la start la final:
bool bfs() {
    queue<int> q;
    anc.clear();
    anc.resize(2*n + 2, -1);
    viz.clear();
    viz.resize(2*n + 2, false);

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

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

        if (curr == final)
            continue;

        for (int i = 1; i <= 2 * n + 1; i++) {
            if (!viz[i] && rez[curr][i] > 0) {
                anc[i] = curr;
                q.push(i);
                viz[i] = true;
            }
        }
    }
    return viz[final];
}

//algoritmul edmonds-karp:
void edmondsKarp() {
    //cat timp mai exista lanturi care pot fi parcurse de la start la final, continuam sa le parcurgem adaugand flux:
    while (bfs()) {
        //pentru toate drumurile care au dus la final:
        for (int i = n+1; i <= 2*n; i++)
        {
            if (!(viz[i] && rez[i][final] != 0))
                continue;
            //caut bottleneck-ul, reprezentand noul flux:
            int aux = i;
            int min = rez[aux][final];
            while (aux != start) {
                if (rez[anc[aux]][aux] < min)
                    min = rez[anc[aux]][aux];
                aux = anc[aux];
            }

            //updatez matricea reziduala, adaugand noul flux:
            aux = i;

            rez[aux][final] -= min;
            rez[final][aux] += min;

            while (aux != start) {
                rez[anc[aux]][aux] -= min;
                rez[aux][anc[aux]] += min;
                aux = anc[aux];
            }

            maxFlow += min;
        }
    }
}


//citirea datelor: trebuie sa modelam datele sub forma unui graf orientat pe care calcularea fluxului maxim va determina arcele de pe harta, astfel
//adaugam doua noduri auxiliare, nodul de start si nodul de final, iar restul nodurilor, cele care reprezinta puncte pe harta, se vor dubla, formand doua multimi
//in care fiecare nod din prima multime va fi unit de toate cele din a doua multime, mai putin de dublura lui
void citire() {
    ifstream fin("harta.in");
    int gInt, gExt;
    fin >> n;

    start = 0;
    final = 2 * n + 1;

    rez.resize(2*n + 2, vector<int>(2*n + 2, 0));
    gradInt.resize(n + 1);
    gradExt.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        fin >> gradExt[i] >> gradInt[i];

        rez[start][i] = gradExt[i];
        rez[i + n][final] = gradInt[i];

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

    fin.close();
}

void afisare() {
    ofstream fout("harta.out");

    fout << maxFlow << "\n";
    for (int i = 1; i <= n; i++)
    {
        for (int j = n + 1; j <= n * 2; j++)
        {
            if (rez[i][j] == 0 && i != j - n)
            {
                fout << i << " " << j - n << "\n";
            }
        }
    }

    fout.close();
}

int main()
{
    citire();
    edmondsKarp();
    afisare();
    return 0;
}