Cod sursa(job #3190755)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 7 ianuarie 2024 22:12:26
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.79 kb
// https://www.infoarena.ro/problema/harta

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <deque>
#include <queue>
#include <fstream>
#include <algorithm>

using namespace std;


struct Edge
{
    int left, right;
};


class Graph
{
private:
    static const int MAX_VERTICES = 100;

    int noVertices;
    int noEdges;

    vector<vector<int>> neighbours;
    vector<vector<int>> capacity;
    vector<vector<int>> flow;

public:
    Graph(const int &noVertices)
        : noVertices(noVertices),
          neighbours(noVertices + 1),
          capacity(noVertices + 1, vector<int>(noVertices + 1, 0)),
          flow(noVertices + 1, vector<int>(noVertices + 1, 0))
    {
    }

    int getNoVertices()
    {
        return noVertices;
    }

    int getNoEdges()
    {
        return noEdges;
    }


    Graph& addNeighbours(const int& vertex1, const int& vertex2)
    {
        neighbours[vertex1].push_back(vertex2);
        neighbours[vertex2].push_back(vertex1);

        return *this;
    }

    Graph& addCapacity(const int& vertex, const int& neighbour, const int& capacity)
    {
        this->capacity[vertex][neighbour] = capacity;

        return *this;
    }


    bool BFS(const int& source, const int& sink, vector<int>& parent)
    {
        parent = vector<int> (noVertices + 1, -2);

        queue<int> que;
        que.push(source);
        parent[source] = -1;

        while (!que.empty())
        {
            int curr_vertex = que.front();
            que.pop();

            if (curr_vertex == sink)
                continue;

            for (int neigh : neighbours[curr_vertex])
            {
                //atunci cand avem muchia inversa, capacitatea este 0
                //deci cand flow-ul este 0, nu putem "intoarce" pe acolo ceva
                //cand flow-ul este diferit de 0 (adica negativ) putem intoarce pe acolo ceva
                if (parent[neigh] != -2 || flow[curr_vertex][neigh] == capacity[curr_vertex][neigh])
                    continue;

                parent[neigh] = curr_vertex;
                que.push(neigh);
            }
        }

        return parent[sink] != -2;

    }

    int generateEdges(vector<Edge>& edges)
    {
        int maxFlow = 0;
        vector<int> parent;

        while(BFS(0, noVertices, parent))
        {
            for (int neigh : neighbours[noVertices])
            {
                int minFlowPath = INT_MAX;

                int curr_vertex = noVertices;
                int curr_parent = neigh;

                for ( ; curr_vertex != 0; curr_vertex = curr_parent, curr_parent = parent[curr_vertex])
                {
                    if (curr_parent == -2)
                    {
                        minFlowPath = 0;
                        break;
                    }

                    //de remarcat ca atunci cand avem o muchie de intoarcere, diferenta o sa fie 
                    //0 - (un flux negativ), deci o sa comparam in continuare cu un numar pozitiv
                    if (capacity[curr_parent][curr_vertex] - flow[curr_parent][curr_vertex] < minFlowPath)
                        minFlowPath = capacity[curr_parent][curr_vertex] - flow[curr_parent][curr_vertex];
                }
                if (minFlowPath == 0)
                    continue;

                maxFlow += minFlowPath;

                curr_vertex = noVertices;
                curr_parent = neigh;
                for ( ; curr_vertex != 0; curr_vertex = curr_parent, curr_parent = parent[curr_vertex])
                {
                    flow[curr_parent][curr_vertex] += minFlowPath;
                    flow[curr_vertex][curr_parent] -= minFlowPath;
                }
            }
        }


        edges = vector<Edge>();
        for (int i = 1; i <= noVertices/2; i++)
            for (int j = 1; j <= noVertices/2; j++)
                if (flow[i][j + noVertices/2] == 1)
                    edges.push_back({i, j});

        return edges.size();
    }
};



int main()
{
    int N, M;

    ifstream fin ("harta.in");
    fin>> N;
    Graph graph(2 * N + 1);

    for (int i=1; i<=N; i++)
    {
        int in, out;
        fin >> in >> out;

        graph.addNeighbours(0, i).addCapacity(0, i, in);


        for (int j=1; j <= N; j++)
            if (i != j)
                graph.addNeighbours(i, j + N).addCapacity(i, j + N, 1);

        graph.addNeighbours(i + N, 2 * N + 1).addCapacity(i + N, 2 * N + 1, out);
    }
    
    fin.close();

    ofstream fout ("harta.out");

    vector <Edge> edges;
    fout << graph.generateEdges(edges) << "\n";
    for (Edge& ed : edges)
        fout << ed.left << " " << ed.right << "\n";

    fout.close();

    return 0;
}