Cod sursa(job #3188080)

Utilizator barzoiusBarzoius barzoius Data 1 ianuarie 2024 16:06:21
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

std::ifstream fin("harta.in");
std::ofstream fout("harta.out");

std::vector<std::vector<int>> F(210, std::vector<int>(210, 0));
std::vector<std::vector<int>> C(210, std::vector<int>(210, 0));

std::vector<int> EDGE_FLOW(210, 0);

std::vector<int>FROM_TO(210, -1);

std::vector<std::vector<int>> ADJ_LIST;


int BFS(int start_vertex, int finish_vertex)
{

    std::queue<int> QUEUE;
    QUEUE.push(start_vertex);

    EDGE_FLOW[start_vertex] = INT16_MAX;

    FROM_TO[start_vertex] = -2;

    while(!QUEUE.empty())
    {
        int vertex = QUEUE.front();
        QUEUE.pop();

        for(int adj_vertex : ADJ_LIST[vertex])
        {
            if(FROM_TO[adj_vertex] == -1)
            {
                if(C[vertex][adj_vertex] - F[vertex][adj_vertex] > 0)
                {
                    FROM_TO[adj_vertex] = vertex;

                    EDGE_FLOW[adj_vertex] = std::min(EDGE_FLOW[vertex],
                                                     C[adj_vertex][vertex] - F[adj_vertex][vertex]);

                    if(adj_vertex == finish_vertex) return EDGE_FLOW[adj_vertex];

                    QUEUE.push(adj_vertex);
                }
            }
        }
    }

    return 0;
}


int EK(int start_vertex, int finish_vertex)
{
    int MAX_FLOW = 0;

    while(true) {

        int FLOW = BFS(start_vertex, finish_vertex);

        if (FLOW == 0) {break;}


        MAX_FLOW = MAX_FLOW + FLOW;

        int vertex = finish_vertex;

        while (vertex != start_vertex)
        {
            int prev_vertex = FROM_TO[vertex];

            F[prev_vertex][vertex] += FLOW;
            F[vertex][prev_vertex] -= FLOW; //rezid

            vertex = prev_vertex;
        }
    }

    return MAX_FLOW;
}

int main()
{
    int N;
    fin >> N;

    int S = 0;
    int E = 2 * N + 1;

    ADJ_LIST.resize(2 * N + 1);

    for(int i = 1 ; i <= N; i++)
    {
        int OUTWARDS, INWARDS;
        fin >> OUTWARDS >> INWARDS;

        C[S][i] = OUTWARDS;
        C[i + N][E] = INWARDS;

        ADJ_LIST[S].emplace_back(i);
        ADJ_LIST[N + i].emplace_back(E);

        for(int j = 1; j <= N; j++)
        {
            if(i != j) //excludem buclele
            {
                C[i][j + N] = 1;
                ADJ_LIST[i].emplace_back(j + N);
                ADJ_LIST[j + N].emplace_back(i);
            }
        }
    }

    int MAX_FLOW = EK(S, E);

    fout << MAX_FLOW << "\n";

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

    fin.close();
    fout.close();
    return 0;
}