Cod sursa(job #2962034)

Utilizator BojneaguBojneagu David-Alexandru Bojneagu Data 7 ianuarie 2023 17:43:00
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>
using namespace std;

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

#define MAX_SIZE 500

vector<int> tata, viz;
int rez[MAX_SIZE][MAX_SIZE], in[MAX_SIZE], out[MAX_SIZE], n, m, src, dest;

int BFS()
{
    tata.clear();
    tata.resize(2 *n + 2, 0);
    viz.clear();
    viz.resize(2 *n + 2, 0);
    queue<int> que;
    que.push(src);
    viz[src] = 1;
    tata[src] = -1;
    while (!que.empty())
    {
        int nod = que.front();

        que.pop();

        if (nod == dest)
            return 1;

        for (int i = 1; i <= 2 *n + 1; i++)
        {
            if (!viz[i] && rez[nod][i] > 0)
            {
                que.push(i);
                tata[i] = nod;
                viz[i] = 1;
            }
        }
    }

    return 0;
}

int FordFulkerson()
{
    int flux_final = 0;
    int flux_curr = 0;
    while (BFS())
    {
        for (int i = 1; i <= n; i++)
        {
            if (viz[n + i] && rez[n + i][2 *n + 1] > 0)	// n+i pt ca le am dublat ca nr de noduri
            {
                flux_curr = INT_MAX;
                tata[dest] = n + i;
                for (int nod = dest; nod != src; nod = tata[nod])
                    flux_curr = min(flux_curr, rez[tata[nod]][nod]);	//get flux

                if (flux_curr == 0)
                    continue;

                for (int nod = dest; nod != src; nod = tata[nod])
                {
                    rez[tata[nod]][nod] -= flux_curr;
                    rez[nod][tata[nod]] += flux_curr;	// actualizare fluxuri
                }

                flux_final += flux_curr;
            }
        }
    }

    return flux_final;
}



int main()
{
    fin >> n;
    src = 0;	// source
    dest = 2 *n + 1;	// destination
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        fin >> y >> x;

        in[i] = x;
        out[i] = y;

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

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

    fout << FordFulkerson() << endl;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (rez[i][j + n] == 0 && i != j)
            {
                fout << i << " " << j << endl;
            }
        }
    }

    fin.close();
    fout.close();
}