Cod sursa(job #3190256)

Utilizator TirilaPatricTirila Patric-Gabriel TirilaPatric Data 7 ianuarie 2024 13:34:39
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <climits>

using namespace std;

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

int N, x, y, drumuri;
vector<vector<int>> list, cap, flow;
int S, T;
vector<int> previous;

void init_previous () {
    for(int i=0; i<=T; i++){
        previous[i] = -1;
    }
}

int bfs () {
    init_previous();

    queue<pair<int, int>> q;
    q.push({0, INT_MAX});

    while (!q.empty()) {
        int town = q.front().first, minFlowUntilNow = q.front().second;
        q.pop();
        for (auto& nextTown : list[town]) {
            if (previous[nextTown] == -1 && cap[town][nextTown] > flow[town][nextTown]) { // daca nu e vizitat deja si daca capacitatea permite sa mergem
                previous[nextTown] = town;
                int residual_flow = cap[town][nextTown] - flow[town][nextTown];
                int minimum_flow_of_path = minFlowUntilNow > residual_flow ? residual_flow : minFlowUntilNow;
                q.push({nextTown, minimum_flow_of_path});

                if (nextTown == T) return minimum_flow_of_path;

            }
        }

    }
    return 0;
}

void edmonds_karp () {
    int town, prevTown;
    while (true) {
        int flow_of_path = bfs();
        if (!flow_of_path) break;

        // DRUM GASIT DE LA START LA SINK CARE DUCE flow_of_path FLOW

        town = T;

        while (S != town) {
            prevTown = previous[town];

            flow[town][prevTown] -= flow_of_path;
            flow[prevTown][town] += flow_of_path;

            town = previous[town];
        }
    }
}

void citire_date () {
    f>>N;
    T = 2*N+1;
    previous.resize(T);
    list.resize(T+1, {});
    cap.assign(T+1, vector<int>(T+1));
    flow.resize(T+1, vector<int>(T+1));

    for (int i=1; i<=N; i++) {
        f>>x>>y; // x = nr drumuri out, y = nr drumuri in
        cout<<x<<" "<<y<<endl;
        drumuri += x;
        for (int j=N+1; j<T; j++) {
            if (i != j - N) {
                list[j].push_back(i);
                list[i].push_back(j);
                cap[i][j] = 1;
            }
        }
        cap[S][i] = x;
        cap[i+N][T] = y;
        list[S].push_back(i);
        list[i].push_back(S);
        list[i+N].push_back(T);
        list[T].push_back(i+N);
    }

}

void rezolvare () {
    citire_date();
    g<<drumuri<<endl;
    edmonds_karp();

    for (int i=1; i<=N; i++) {
        for (int j=N+1; j<T; j++) {
            if (flow[i][j]) {
                g<<i<<" "<<j-N<<endl;
            }
        }
    }
}

int main () {
    rezolvare();
    return 0;
}