Cod sursa(job #3359505)

Utilizator rares89_Dumitriu Rares rares89_ Data 29 iunie 2026 13:01:12
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, source, sink;
vector<vector<int>> C, G;
vector<int> parent;
vector<pair<int, int>> sol;

bool bfs(int start, int end) {
    vector<bool> visited(2 * n + 2, false);
    queue<int> Q;
    Q.push(start);
    visited[start] = true;

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

        for (int neighbor : G[node]) {
            if (!visited[neighbor] && C[node][neighbor] > 0) {
                parent[neighbor] = node;
                visited[neighbor] = true;

                if (neighbor == end)
                    return true;

                Q.push(neighbor);
            }
        }
    }

    return false;
}

int eKarp(int start, int end) {
    int maxFlow = 0;

    while (bfs(start, end)) {
        int pathFlow = 2e9;

        for (int v = end; v != start; v = parent[v]) {
            int u = parent[v];
            pathFlow = min(pathFlow, C[u][v]);
        }

        for (int v = end; v != start; v = parent[v]) {
            int u = parent[v];
            C[u][v] -= pathFlow;
            C[v][u] += pathFlow;
        }

        maxFlow += pathFlow;
    }

    return maxFlow;
}

int main() {
    fin >> n;

    source = 0;
    sink = 2 * n + 1;

    C.resize(2 * n + 2, vector<int>(2 * n + 2, 0));
    G.resize(2 * n + 2);
    parent.resize(2 * n + 2);

    for (int i = 1; i <= n; ++i) {
        int x, y;
        fin >> x >> y;

        G[source].push_back(i);
        G[i].push_back(source);
        C[source][i] = x;

        G[n + i].push_back(sink);
        G[sink].push_back(n + i);
        C[n + i][sink] = y;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j) {
                G[i].push_back(n + j);
                G[n + j].push_back(i);
                C[i][n + j] = 1;
            }
        }
    }

    eKarp(source, sink);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j && C[n + j][i] == 1)
                sol.push_back({i, j});
        }
    }

    fout << sol.size() << "\n";

    for (auto edge : sol) {
        fout << edge.first << " " << edge.second << "\n";
    }
    
    return 0;
}