Cod sursa(job #3333749)

Utilizator G3K0Airinei Gabriel Vlad G3K0 Data 14 ianuarie 2026 23:55:01
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

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

const int INF = 1e9;
const int MAXN = 105; 

int N;
int capacity[2 * MAXN][2 * MAXN];
int parent[2 * MAXN];
vector<int> adj[2 * MAXN];

void add_edge(int u, int v, int cap) {
    adj[u].push_back(v);
    adj[v].push_back(u); 
    capacity[u][v] = cap;
}

int bfs(int s, int t) {
    fill(parent, parent + 2 * N + 2, -1);
    parent[s] = -2;
    queue<pair<int, int>> q;
    q.push({s, INF});

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

        for (int v : adj[u]) {
            if (parent[v] == -1 && capacity[u][v] > 0) {
                parent[v] = u;
                int new_flow = min(flow, capacity[u][v]);
                if (v == t)
                    return new_flow;
                q.push({v, new_flow});
            }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0;
    int new_flow;

    while (new_flow = bfs(s, t)) {
        flow += new_flow;
        int cur = t;
        while (cur != s) {
            int prev = parent[cur];
            capacity[prev][cur] -= new_flow;
            capacity[cur][prev] += new_flow;
            cur = prev;
        }
    }
    return flow;
}

int main() {

    fin >> N;

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

    int total_edges = 0;

    for (int i = 1; i <= N; ++i) {
        int dout, din;
        fin >> dout >> din;
        
        add_edge(S, i, dout);
        
        add_edge(N + i, D, din);
        
        for (int j = 1; j <= N; ++j) {
            if (i != j) {
                add_edge(i, N + j, 1);
            }
        }
    }

    max_flow(S, D);

    vector<pair<int, int>> result_edges;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (i == j) continue;
            
             if (capacity[i][N + j] == 0) {
                result_edges.push_back({i, j});
            }
        }
    }

    fout << result_edges.size() << "\n";
    for (auto p : result_edges) {
        fout << p.first << " " << p.second << "\n";
    }

    return 0;
}