Cod sursa(job #2962558)

Utilizator radubuzas08Buzas Radu radubuzas08 Data 8 ianuarie 2023 18:47:55
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.42 kb
/*
 * COmplexitate timp O(n * m^2)
 *
 * Algoritm folosit: Edmonds-Karp
 *
 * Am un graf cu n noduri in "partea stanga" si un graf cu n noduri in "partea dreapta".
 * Am o muchie intre nodul i din partea stanga si nodul j din partea dreapta daca i != j, unde 1 <= i, j <= n.
 *
 * Practic am un graf bipartit cu n * (n - 1) muchii. Fiecare muchie are capacitatea 1.
 *
 * Creez o SuperSursa si un SuperSink.
 *
 * Pentru fiecare nod din partea stanga, creez o muchie de la SuperSursa la nodul respectiv. Capacitatea muchiei
 * va fi corelata cu gradul de iesire al nodului respectiv.
 *
 * Pentru fiecare nod din partea dreapta, creez o muchie de la nodul respectiv la SuperSink. Capacitatea muchiei
 * va fi corelata cu gradul de intrare al nodului respectiv.
 *
 * Aplic algoritmul de flux pe graful rezultat.
 * In graful rezidual, muchiile saturate care pleaca din nodurile din partea stanga a grafului sunt muchiile care
 * formeaza cuplajul maxim. Astfel, fluxul maxim este egal cu numarul de muchii din cuplajul maxim.
 *
 * Afisez muchiile care fac parte din cuplajul maxim.
 *
 * P.S.: implementarea este APROAPE identica cu cea din flux-max( exercitiul 1 ), aici folosesc matrice pentru flow
 * si capacitate, cuplat cu lista de adiacenta a grafului, la flux-max folosesc lista de adiacenta pentru ID-ul muchiei
 * si un vector de muchii.
 * */

#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");
class Flow
{
    int source, sink;
    int n;
    int maxFlow;
    std::vector<bool> visited;
    std::vector<std::vector<int> > graph;
    std::vector<std::vector<int> > capacity;
    std::vector<std::vector<int> > flow;
    std::vector<int> father;

//    void dfs(int x) {
//        visited[x] = true;
//        for (int node : graph[x]) {
//            if (!visited[node] && flow[x][node] < capacity[x][node]) {
//                dfs(node);
//            }
//        }
//    }

    bool bfs()
    {
        visited.assign(n+1, false);
        std::queue<int> q;
        q.push(source);
        visited[source] = true;

        while(!q.empty())
        {
            int node = q.front();
            q.pop();

            for(int neighbour : graph[node])
            {
                if(capacity[node][neighbour] == flow[node][neighbour] || visited[neighbour])  // muchie saturata sau vizitat
                    continue;
                visited[neighbour] = true;
                q.push(neighbour);
                father[neighbour] = node;
                if(neighbour == sink)       //  daca am ajuns la sink, am gasit un drum de ameliorare/crestere
                    return true;
            }
        }
        return false;
    }


public:
    Flow(int n, int source, int sink)
    {
        this->source = source;
        this->sink = sink;
        this->n = n;
        this->maxFlow = 0;
        capacity.resize(n + 1, std::vector<int>(n + 1));
        flow.resize(n + 1, std::vector<int>(n + 1));
        graph.resize(n + 1);
        visited.resize(n + 1);
        father.resize(n + 1);
    }

    void addEdge(int x, int y, int cost = 1)
    {
        if(capacity[x][y] == 0)
        {
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        capacity[x][y] += cost;
    }

    int getMaxFlow()
    {
        maxFlow = 0;
        do{
            if( !bfs() )
                break;
            for (auto nod : graph[sink]) {
                if(capacity[nod][sink] == flow[nod][sink] || visited[nod] == 0)     //  muchie saturata sau nu am ajuns la nod
                    continue;

                father[n] = nod;
                int flowMin = 0x7fffffff;
                for (int i = sink; i != source; i = father[i])
                    flowMin = std::min(flowMin, capacity[father[i]][i] - flow[father[i]][i]);
                if (flowMin == 0)
                    continue;

                maxFlow += flowMin;
                for (int i = sink; i != source; i = father[i]) {
                    flow[father[i]][i] += flowMin;
                    flow[i][father[i]] -= flowMin;
                }
            }
        } while (true);
        return maxFlow;
    }

    int getFlow() const{
        return maxFlow;
    }

//    std::vector<std::pair<int, int>> getMinCut()
//    {
//        visited.assign(n+1, false);
//        for (int i = 1; i <= n/2; ++i) {
//            flow[source][i] = 0;
//        }
//
//        dfs(source);
//        std::vector<std::pair<int, int>> minCut;
//        for (int i = source; i <= sink; ++i) {
//            for (int j : graph[i]) {
//                if (visited[i] && !visited[j] && capacity[i][j] > 0)
//                    minCut.emplace_back(i, j);
//            }
//        }
//        return minCut;
//    }

    void printGraph() {
        for (int i = 1; i <= n/2; ++i)      //  partea stanga
            for (int j = n/2; j <= n; ++j)  //  partea dreapta
                if (flow[i][j] > 0)         //  muchie saturata
                    out << i << ' ' << j - n/2 << '\n';
    }

};

int main() {
    int n;
    in >> n;
    Flow f(2 * n + 1, 0, 2 * n + 1);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i != j)
                f.addEdge(i, j + n);

    int x, y;
    for (int i = 1; i <= n; ++i) {
        in >> x >> y;
        f.addEdge(0, i, x);
        f.addEdge(n + i, 2 * n + 1, y);
    }
    in.close();

    int sol = f.getMaxFlow();

    out << sol << '\n';
    f.printGraph();
    out.close();
    return 0;
}