Cod sursa(job #2970181)

Utilizator ArthurelVilceanu Razvan-Arthur Arthurel Data 24 ianuarie 2023 14:12:31
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
// Se creeaza un graf complet de n noduri. In stanga nodurile propriu zise si in dreapta copiile lor
// Se initializeaza muchia dintre ele cu capacitatea 1
// Se leaga nodurile de un nod fictiv 0 pentru gradul intern si o copie a nodurilor de nodul fixtiv 2*n+1
// Se foloseste un bfs pentru a traversa graful si se calculeaza flow-ul minim
// Se parcurge drumul si se scade din flow ul fiecarui nod flow ul minim
// Flow-ul maxim va fi numarul de drumri si pentru a afisa drumurile se va itera vectorul de capacitati si se vor extrage perechile de noduri cu capacitatile 1

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

vector<vector<int>> adj_list;
vector<int> parent;

int N, dest, x,y, capacity[201][201], maxim=1000000;
long max_flow = 0;

//parcurgere de tip BFS
bool bfs()
{
    vector<bool> viz(2 * N + 1);
    queue<int> q;
    q.push(0);
    viz[0] = true;
    parent[0] = -1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto v: adj_list[u])
        {
            if(viz[v]==false && capacity[u][v]!=0)
            {
                parent[v] = u;
                if(v == dest)
                    return true;
                viz[v] = true;
                q.push(v);
            }
        }
    }
    return false;
}




int main()
{
    f >> N;
    dest= 2 * N + 1;
    adj_list.resize(201);
    parent.resize(2 * N + 1);

     // Initializare

    for(int i=1; i <= N; i++)
        for(int j= 1 + N; j <= 2 * N; j++)
        {
            if(i!= j - N)
            {
                adj_list[i].push_back(j);
                adj_list[j].push_back(i);
                capacity[i][j]=1;
            }
        }

   // Legare noduri de nodul 0 si 2*n+1 pentru gradele interne si externe

    for(int i=1; i <= N; i++)
    {
        f >> x >> y;
        adj_list[0].push_back(i);
        adj_list[i].push_back(0);
        adj_list[dest].push_back(i + N);
        adj_list[i + N].push_back(dest);
        capacity[0][i]=x;
        capacity[i + N][dest]=y;
    }

    while(bfs())
    {
        int aux, next=dest, path_flow = maxim;
        while(next != 0)
        {
            aux = parent[next];
            path_flow=min(capacity[aux][next],path_flow);
            next = parent[next];
        }
        next=dest;
        while(next != 0)
        {
            aux = parent[next];
            capacity[aux][next] -= path_flow;
            capacity[next][aux] += path_flow;
            next = parent[next];
        }
        max_flow = max_flow + path_flow;
    }
    g<<max_flow<<"\n";

    // Afisare
    for(int i=1; i <= N; i++)
        for(int j= 1 + N; j <= 2 * N; j++)
        {
            if(capacity[j][i])
                g << i << j - N << "\n";
        }
    return 0;
}