Cod sursa(job #2684985)

Utilizator stanciucalinStanciu Calin stanciucalin Data 15 decembrie 2020 15:41:43
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;

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

const int INF = 1000000000;

int n_nodes;
int * g_in;
int * g_out;

vector <pair <int, int>> m_list;

int n;
unordered_map <int, int> * lv;

bool BFS(int t[]){

    bool * viz = new bool [n + 1];

    t[1] = 0;

    for(int i = 1; i <= n; i++)
        viz[i] = 0;

    viz[1] = 1;

    queue <int> q;
    q.push(1);

    while(!q.empty()){

        int current_node = q.front();
        q.pop();

        for(auto & next : lv[current_node]){

            if(next.first == n){

                t[n] = current_node;

                return 0;
            }
            else if(!viz[next.first]){

                t[next.first] = current_node;
                viz[next.first] = 1;

                q.push(next.first);
            }
        }
    }

    return 1;
}

void Edmonds_Karp(){

    bool path_not_found;

    int * t = new int [n + 1];

    do{

        path_not_found = BFS(t);

        if(!path_not_found){

            /// prima iteratie prin vectorul de tati, pentru a determina muchia de capacitate minima

            int min_capacity = INF;

            int node = n;
            while(t[node]){

                int current_capacity = lv[t[node]][node];

                if(current_capacity < min_capacity)
                    min_capacity = current_capacity;

                node = t[node];
            }

            /// a doua iteratie pentru a modifica graful rezidual

            node = n;
            while(t[node]){

                int current_capacity = lv[t[node]][node];

                if(current_capacity == min_capacity){

                    lv[t[node]].erase(node);
                }
                else
                    lv[t[node]][node] -= min_capacity;

                if(lv[node].find(t[node]) != lv[node].end()){

                    lv[node][t[node]] += min_capacity;
                }
                else
                    lv[node][t[node]] = min_capacity;

                node = t[node];
            }

        }

    }
    while(!path_not_found);
}

int main(){

    f >> n_nodes;

    g_in = new int [n_nodes + 1];
    g_out = new int [n_nodes + 1];

    int x, y;
    for(int i = 1; i <= n_nodes; i++){

        f >> x >> y;

        g_out[i] = x;
        g_in[i] = y;
    }

    /// pregatire apelare edmonds karp

    /// cate o clona pentru fiecare nod, plus un nod de start si unul de final
    /// voi avea codificarea:
    /// 1 -> nodul sursa
    /// 2 .. n_nodes + 1 -> primul rand de noduri
    /// n_nodes + 2 .. n_nodes + n_nodes + 1 -> al doilea rand de noduri
    /// n_nodes * 2 + 2 -> nodul destinatie

    n = 2 + n_nodes * 2;

    lv = new unordered_map <int, int> [n + 1]; ///lista de vecini in noul graf

    for(int node = 2; node <= n_nodes + 1; node++){

        if(g_out[node - 1])
            lv[1][node] = g_out[node - 1];

        for(int clone = n_nodes + 2; clone <= n_nodes + n_nodes + 1; clone++){

            if(clone - n_nodes != node)
                lv[node][clone] = 1;
        }

        if(g_in[node - 1])
            lv[node + n_nodes][n_nodes * 2 + 2] = g_in[node - 1];
    }

    Edmonds_Karp();

    for(int clone = n_nodes + 2; clone <= n_nodes + n_nodes + 1; clone++){

        for(auto & node : lv[clone]){

            m_list.push_back(pair <int, int> (node.first, clone - n_nodes));
        }
    }

    g << m_list.size() << '\n';

    for(int i = 0; i < m_list.size(); i++)
        g << m_list[i].first - 1 << " " << m_list[i].second - 1 << '\n';

    return 0;
}