Cod sursa(job #2958835)

Utilizator Alexandru_PotangaPotanga Alexandru Alin Alexandru_Potanga Data 28 decembrie 2022 15:53:05
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int graf[201][201];
int tati[201];
bool vizitat[201];
bool bfs(int n)
{
    queue<int> coada;

    for(int i = 0; i <= n; i++)
    {
        vizitat[i] = false;
        tati[i] = -1;
    }

    coada.push(0);
    vizitat[0] = true;

    while(coada.empty() == false)
    {
        int nod = coada.front();
        coada.pop();

        for(int i = 0; i <= n; i++)
        {
            if(graf[nod][i] > 0 && vizitat[i] == false)
            {
                coada.push(i);
                vizitat[i] = true;
                tati[i] = nod;
                if(i == n)
                {
                    return true;
                }
            }
        }
    }

    return false;
}
int flux(int n)
{
    int flux_maxim = 0;
    while(bfs(n))
    {
        for(int i = 1; i < n; i++)
        {
            if(graf[i][n] > 0 && vizitat[i] == true)
            {
                int penultim = i;

                vector<int> drum_c;
                drum_c.push_back(n);
                drum_c.push_back(penultim);

                int tata = tati[penultim];
                while(tata != -1)
                {
                    drum_c.push_back(tata);
                    tata = tati[tata];
                }

                int bottleneck = 2;

                for(int i = 1; i < drum_c.size(); i++)
                {
                    bottleneck = min(bottleneck, graf[drum_c[i]][drum_c[i-1]]);
                }

                flux_maxim = flux_maxim + bottleneck;

                for(int i = 1; i < drum_c.size(); i++)
                {
                    graf[drum_c[i]][drum_c[i-1]] = graf[drum_c[i]][drum_c[i-1]] - bottleneck;
                    graf[drum_c[i-1]][drum_c[i]] = graf[drum_c[i-1]][drum_c[i]] + bottleneck;
                }
            }
        }
    }

    return flux_maxim;
}
int main()
{
    int n;

    f >> n;

    int a, b;

    for(int i = 1; i <= n; i++)
    {
        f >> a >> b;
        graf[0][i] = a;
        graf[i + n][n * 2 + 1] = b;
    }

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


    g << flux(2 * n + 1) << "\n";

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

    return 0;
}