Cod sursa(job #3193881)

Utilizator mihaibivolBivol Mihai mihaibivol Data 15 ianuarie 2024 22:25:13
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.86 kb
//logica avem n noduri cele originale si n copii. 
//din start plecam cu ce vrea sa iasa din nod
//in t venim cu vrea sa intre in nod
//si asa se rezolva (e prea mistoo)
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <fstream>
using namespace std;

struct Edge{
    int node;
    int flow;
    int capacity;
    int reverse; //stores an index of reverse edge
};
class Graf {
    int Nodes;
    int* level;
    vector<Edge>* adj;

    public:
        Graf(int Nodes){
            adj = new vector<Edge>[Nodes];
            this->Nodes = Nodes;
            level = new int[Nodes]; 
        }
        void adaugare_muchie(int node1, int node2, int cost){
            Edge a{node2, 0, cost, (int)adj[node2].size() };

            //reverse edge
            Edge b{node1, 0, 0, (int)adj[node1].size() };

            adj[node1].push_back(a);
            adj[node2].push_back(b);//reverse edge
        }
        //functie doar pt aceasta problema
        vector<pair<int,int>> get_muchii(int start, int finish){
            vector<pair<int,int>> result;
            for(int i = start; i <= finish; i ++){
                for(auto &muchie: adj[i]){
                    if(muchie.flow == 1){
                        result.push_back(make_pair(i,muchie.node - finish)); //acest -N este specific doar acestei probleme
                    }
                }
            }
            return result;
        }
        bool BFS(int s, int t);
        int DFSFlow(int s, int flow, int t, int ptr[]);
        int MaxFlowDinic(int s, int t);

};

bool Graf::BFS(int s, int t){
    for(int i = 0; i < Nodes; i ++){
        level[i] = -1;
    }
    level[s] = 0; //nivelul de start e 0

    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        //mergem prin vecinii nodului curent
        for(auto i = adj[current].begin(); i != adj[current].end(); i ++){
            Edge& vecin = *i; //se preia vecinul

            //verificam daca am mai trecut prin el si daca nu este terminat
            if(level[vecin.node] < 0 && vecin.flow < vecin.capacity){
                level[vecin.node] = level[current] + 1;

                q.push(vecin.node);
            }
        }
    }
    //daca nu putem ajunge la sink (t) returnam fals
    return level[t] < 0 ? false : true;
}

//un dfs folosit dupa ce se afla nivelul cu BFS. 
int Graf::DFSFlow(int node, int flow, int t, int start[]){
    if(node == t) return flow;

    for(; start[node] < adj[node].size(); start[node]++){
        Edge& next = adj[node][start[node]];
        //daca mergem inainte cu DFS-ul si muchia nu e terminata
        if(level[next.node] == level[node] + 1 && next.flow < next.capacity){
            //aflam flowul minim de la node la sink (t)
            int curr_flow = min(flow, next.capacity - next.flow);

            int temp_flow = DFSFlow(next.node, curr_flow, t, start);

            if(temp_flow > 0){
                //dupa ce aflam valoarea maxima care o putem duce din node in t
                //punem in toate drumurile pana acolo
                next.flow += temp_flow;

                adj[next.node][next.reverse].flow -= temp_flow;
                return temp_flow;
            }
        }
    }

    return 0;
}

//aici se vor schimba si valorile din vector<Edge>.
int Graf::MaxFlowDinic(int s, int t){
    if( s == t)return - 1;

    int total = 0; 
    //facem caclulul de bfs pana cand nu mai putem ajunge la sink(t)
    while(BFS(s,t) == true){
        int *start = new int[Nodes + 1]{0};

        while(int flow = DFSFlow(s, INT_MAX, t, start)){
            total+= flow;
        }
        delete[] start;

    }
    return total;
}

int main(){
    ifstream fin("harta.in");
    ofstream fout("harta.out");
    int N;
    fin >> N;
    Graf g(2*N + 3);
    //acum punem muchiile de la start la fiecare nod
    //punem muchii de la copie la sfarsit

    //adaugam muchie de la fiecare nod la copiile afarente
    for(int i = 1; i <= N; i ++)
        for(int j = N + 1 ; j <= 2*N; j ++)
            if(j - N != i)
                g.adaugare_muchie(i,j,1);
    
    for(int i = 1; i <= N ; i ++){
        int intrare, iesire;
        fin >> intrare >> iesire;
        //2*N + 1 = s (inceput), 2*N + 1 = t (sfarsit)
        g.adaugare_muchie(2*N + 1, i, intrare);
        g.adaugare_muchie(i + N, 2*N + 2, iesire);
    }
    //aici se face fluxul si se returneaza cate muchii au fost folosite
    int n = g.MaxFlowDinic(2*N + 1, 2*N + 2);

    //apelam functia din graf care ne da muchiile care au fost schimbate
    //respectiv muchiile care au flow 1 cu cost 1 din graf
    // si care nu au o legatura cu s si t
    vector<pair<int,int>> muchii = g.get_muchii(1,N); //este o functie custom doar de pentru aceasta problema

    //afisarea rezultatului

    fout << n << endl;
    for(int i = 0; i < muchii.size(); i ++){
        fout << muchii[i].first << " " << muchii[i].second << endl;
    }
    return 0;
}