Cod sursa(job #3189553)

Utilizator ingeauaIngeaua Alexandru ingeaua Data 6 ianuarie 2024 10:09:32
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

// Nmax = 202 (s = 0, 100 noduri originale, 100 copii, t = 201)

int capacitate[205][205], matriceFlux[205][205];
vector <int> listaAdiacenta[205];
int tati[205];
int N;
int nrMuchii;

void afiseazaListaAdiacenta(int n)
{
    for (int i = 0; i <= n; i++) 
    {
        cout << "Nodul " << i << " adiacent cu: ";
        for (int j = 0; j < listaAdiacenta[i].size(); j++) 
        {
            cout << listaAdiacenta[i][j] << " ";
        }
        cout << endl;
    }
}

void afiseazaCapacitate()
{
    int n = 2 * N + 1;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            cout << capacitate[i][j] << " ";
        }
        cout << endl;
    }
}

void afiseazaMatriceFlux()
{
    int n = 2 * N + 1;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            cout << matriceFlux[i][j] << " ";
        }
        cout << endl;
    }
}

int bfs(int start, int stop)
{
    vector <int> fluxIesire(205, 0); // fluxul care iese din fiecare nod la pasul curent

    for (int i = 0; i <= 2 * N + 1; i++)
    {
        tati[i] = -1;
    }

    queue<int> coada;
    coada.push(start);
    tati[start] = -2;
    fluxIesire[start] = 999999999;

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

        // luam toti vecinii
        for (int vecin : listaAdiacenta[nod])
        {
            // daca n am ajuns pe un vecin
            if (tati[vecin] == -1)
            {
                // daca putem sa bagam flux in el
                if (capacitate[nod][vecin] - matriceFlux[nod][vecin] > 0)
                {
                    tati[vecin] = nod;
                    fluxIesire[vecin] = min(fluxIesire[nod], capacitate[nod][vecin] - matriceFlux[nod][vecin]);

                    if (vecin == stop)
                    {
                        return fluxIesire[stop];
                    }
                    coada.push(vecin);
                }
            }
        }
    }
}

int edmondsKarp(int start, int stop)
{
    int fluxMax = 0;

    while (fluxMax != nrMuchii)
    {
        // cu bfs gasim fluxul -> drumul cel mai scurt de ameliorare (augumenting path)
        int flux = bfs(start, stop); 

        // daca nu mai avem augumenting path e pa pa
        if (!flux)
        {
            break;
        }

        // crestem fluxul maxim
        fluxMax += flux;

        // refacem drumul fluxului si actualizam matricea de flux
        // nod = nodul pe care suntem in momentul ala
        int nod = stop;
        while (nod != start)
        {
            int anterior = tati[nod];
            matriceFlux[anterior][nod] += flux;
            matriceFlux[nod][anterior] -= flux;
            nod = anterior;
        }
    }

    return fluxMax;
}

int main()
{
    int s, t;
    fin >> N;
    s = 0;
    t = N * 2 + 1;

    // la citire: pt fiecare nod facem o copie (d asta e matricea "dubla" ca dimensiune)
    // facem legaturi sursa -> original cu capacitate = grad extern pt toate nodurile
    // si copie -> sink (final) cu capacitate = grad intern pt toate nodurile
    // apoi pt fiecare pereche (i j) cu i != j facem original i -> copie j cu capacitate = 1
    // si copie j -> original i cu capacitate = 1


    for (int i = 1; i <= N; i++)
    {
        int exterior, interior;
        fin >> exterior >> interior;
        nrMuchii += exterior;

        capacitate[s][i] = exterior;
        capacitate[i + N][t] = interior;

        listaAdiacenta[s].push_back(i);
        listaAdiacenta[i + N].push_back(t); 

        for (int j = N + 1; j <= 2 * N; j++)
        {
            if (i % N != j % N)
            {
                capacitate[i][j] = 1;
                listaAdiacenta[i].push_back(j);
                listaAdiacenta[j].push_back(i);
            }
        } 
    }

    fout << edmondsKarp(s, t) << endl;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (matriceFlux[i][j + N] > 0)
            {
                fout << i << " " << j << endl;
            }
        }
    }

    return 0;
}