Cod sursa(job #2960214)

Utilizator Diana_14Diana Muscalu Diana_14 Data 3 ianuarie 2023 19:18:15
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <bits/stdc++.h>
#define dim 220
#define inf INT_MAX

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");
int tata[dim], a[dim][dim], gradin[dim], gradout[dim], n, m, nod, flow, maxFlow;
bool viz[dim];

///algoritmul clasic de bfs pt max flow doar ca in loc de t am 2n+1
bool bfs()
{
    queue<int> coada;
    ///initializam vectorul de tati cu 0, iar cel de viz cu false
    memset(tata, 0, sizeof(tata));
    memset(viz, false, sizeof(viz));

    coada.push(0);
    viz[0] = true;
    tata[0] = -1;

    while (!coada.empty())
    {
        int node = coada.front();
        coada.pop();

        if (node == 2 * n + 1)
            return true;


        for (int i = 1; i <= 2 * n + 1; i++)
        {
            if (!viz[i] && a[node][i] > 0)
            {
                coada.push(i);
                viz[i] = true;
                tata[i] = node;
            }
        }
    }
    return false;
}
void citireDate()
{
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> gradout[i] >> gradin[i];
        ///adaugam un nou start si un nou final(cu muchii de capacitati egale cu gradele out, respectiv in),
        ///si dublam nodurile, ca sa-l putem lega pe fiecare cu fiecare
        ///2n+1 fiind t-ul
        a[0][i] = gradout[i];
        a[n + i][2 * n + 1] = gradin[i];

        for (int j = 1; j <= n; j++)
            if (i != j)
                a[i][n + j] = 1;
    }
}
void reglamFlow()
{
    while (bfs())
    {
        for (int i = 1; i <= n; i++)
        {
            ///daca a fost vizitat si daca a ajuns la destinatie
            if (viz[n + i] && a[n + i][2 * n + 1] > 0) {
                flow = inf;
                tata[2 * n + 1] = n + i;

                ///parcurgem lantul de la T la S si luam minimul(iP)
                for (nod = 2 * n + 1; nod != 0; nod = tata[nod])
                    flow = min(flow, a[tata[nod]][nod]);
                if (flow == 0)
                    continue;

                ///reglam flow-ul
                for (nod = 2 * n + 1; nod != 0; nod = tata[nod])
                {
                    a[tata[nod]][nod] -= flow;
                    a[nod][tata[nod]] += flow;
                }

                ///adaugam iP ul la flow ul total
                maxFlow += flow;
            }
        }
    }
}

int main() {

    citireDate();
    reglamFlow();

    g << maxFlow << '\n';
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            if (a[i][n + j] == 0 && i != j)
                g << i << " " << j << '\n';
    }

    return 0;
}