Cod sursa(job #2965865)

Utilizator cosminnnnnnnaDuca Cosmina cosminnnnnnna Data 16 ianuarie 2023 13:57:11
Problema Taramul Nicaieri Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, sursa, destinatie;
vector<vector<int>> graf;
vector<int> parinte;
int capacitate[201][201];

bool bfs()
{
    vector<int> vizitat(destinatie);
    queue<int> q;

    q.push(sursa);

    vizitat[sursa] = 1;
    parinte[sursa] = -1;

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

        for (auto v:graf[u])
        {
            if (vizitat[v] == 0 && capacitate[u][v] != 0)
            {
                parinte[v] = u;

                if(v == destinatie)
                    return true;

                vizitat[v] = 1;
                q.push(v);
            }
        }
    }

    return false;
}


int EdmondsKarp()
{
    int fluxMax = 0;

    //cat inca exista un drum neviz
    while(bfs())
    {
        int nod1, nod2;
        nod2 = destinatie;

        int capDrum = INT_MAX;

        //parcurgere drum pentru a cauta capacitatea minima
        while(nod2 != sursa)
        {
            nod1 = parinte[nod2];

            if(capacitate[nod1][nod2] < capDrum)
                capDrum=capacitate[nod1][nod2];

            nod2 = parinte[nod2];
        }

        nod2 = destinatie;

        //parcurgere drum pt a actualiza capacitatile muchiilor
        while(nod2 != sursa)
        {
            nod1 = parinte[nod2];

            capacitate[nod1][nod2] -= capDrum; // cap muchiei din graful initial scade
            capacitate[nod2][nod1] += capDrum; // cap muchiei inverse creste

            nod2=parinte[nod2];
        }

        fluxMax = fluxMax + capDrum;
    }


    return fluxMax;
}

void afisare()
{
    fout << EdmondsKarp() << endl;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (capacitate[j + n][i] == 1)
                fout << i << " " << j << endl;
}


int main()
{
    fin >> n;

    sursa = 0;
    destinatie = 2 * n + 1;

    parinte.resize(2 * n + 1);
    graf.resize(201);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
            {
                graf[i].push_back(j + n);
                graf[j + n].push_back(i);

                capacitate[i][j + n] = 1;
            }
        }

    int a, b;
    for (int i = 1; i <= n; i++)
    {
        fin >> a >> b;

        graf[sursa].push_back(i);
        graf[i].push_back(sursa);

        capacitate[sursa][i] = a;

        graf[destinatie].push_back(i + n);
        graf[i + n].push_back(destinatie);

        capacitate[i + n][destinatie] = b;
    }

    afisare();

    return 0;
}