Cod sursa(job #3189632)

Utilizator annna7Pecheanu Anna annna7 Data 6 ianuarie 2024 12:42:01
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <iostream>

using namespace std;

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

struct Edge {
    int to;
    int flow;
    int capacity;
    int reverse;
};

class Network {
    int V;
    int source, sink;
    vector<int> ptr;
    vector<int> level;
    vector<vector<Edge>> adj;
public:
    Network(int V, int source = -1, int sink = -1) {
        this->V = V;
        this->source = source == -1 ? 0 : source;
        this->sink = sink == -1 ? V - 1 : sink;
        adj.resize(V);
        level.resize(V, -1);
        ptr.resize(V);
    }

    void addEdge(int u, int v, int capacity) {
        Edge a{v, 0, capacity, (int)adj[v].size()};
        Edge b{u, 0, 0, (int)adj[u].size()};

        adj[u].push_back(a);
        adj[v].push_back(b);
    }

    bool BFS();
    int DFS(int node, int bottleneck, int t);
    int getMaxFlow();
    vector<pair<int, int>> getMatches();
};

bool Network::BFS() {
    level.assign(V, -1);
    level[source] = 0;

    queue<int> q;
    q.emplace(source);

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

        for (auto &edge: adj[u]) {
            if (level[edge.to] == -1 && edge.flow < edge.capacity) {
                level[edge.to] = level[u] + 1;
                q.emplace(edge.to);
            }
        }
    }

    return level[sink] != -1;
}

int Network::DFS(int node, int bottleneck, int dest) {
    if (node == dest) {
        return bottleneck;
    }

    for (; ptr[node] < adj[node].size(); ptr[node]++) {
        Edge &e = adj[node][ptr[node]];

        if (level[e.to] == level[node] + 1 && e.flow < e.capacity) {
            int currBottleneck = min(bottleneck, e.capacity - e.flow);
            int updatedBottleneck = DFS(e.to, currBottleneck, dest);

            if (updatedBottleneck > 0) {
                e.flow += updatedBottleneck;
                adj[e.to][e.reverse].flow -= updatedBottleneck;
                return updatedBottleneck;
            }
        }
    }

    return 0;
}

int Network::getMaxFlow() {
    int totalFlow = 0, bottleneck;
    while (BFS()) {
        ptr.assign(V, 0);
        while (bottleneck = DFS(source, INT_MAX, sink)) {
            totalFlow += bottleneck;
        }
    }
    return totalFlow;
}

vector<pair<int, int>> Network::getMatches() {
    vector<pair<int, int>> matches;

    for (int i = 0; i < (V - 2) / 2; ++i) {
        for (auto &neighEdge: adj[i]) {
            if (neighEdge.flow == 1 && neighEdge.to != source && neighEdge.to != sink) {
                matches.emplace_back(i, neighEdge.to);
            }
        }
    }

    return matches;
}

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

    int src = 2 * N, dest = 2 * N + 1;
    Network network(2 * N + 2, src, dest);

    for (int i = 0; i < N; ++i) {
        for (int j = N; j < 2 * N; ++j) {
            if (i != j - N) {
                network.addEdge(i, j, 1);
            }
        }
    }

    int x, y;
    for (int i = 0; i < N; ++i) {
        fin >> x >> y;
        network.addEdge(src, i, x);
        network.addEdge(i + N, dest, y);
    }

    network.getMaxFlow();

    auto answer = network.getMatches();

    fout << answer.size() << endl;
    for (auto &x: answer) {
        fout << x.first + 1 << " " << x.second + 1 - N << '\n';
    }

    return 0;
}