Cod sursa(job #3178578)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 1 decembrie 2023 22:21:13
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <bits/stdc++.h>
using namespace std;

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

class Network {
private:
  bool bfs() {
    fill(level.begin(), level.end(), -1);
    queue<int> Q;
    Q.push(source);
    level[source] = 0;
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto &e : G[u]) {
        if (level[e.to] == -1 && e.flow < e.capacity) {
          level[e.to] = level[u] + 1;
          Q.push(e.to);
        }
      }
    }
    return level[sink] != -1;
  }
  int dfs(int u, int can_push) {
    if (u == sink) {
      return can_push;
    }
    for (int &i = index[u]; i < (int)G[u].size(); ++i) {
      auto &e = G[u][i];
      if (level[e.to] == level[u] + 1 && e.flow < e.capacity) {
        int flow = dfs(e.to, min(can_push, e.capacity - e.flow));
        if (flow > 0) {
          e.flow += flow;
          G[e.to][e.reverse].flow -= flow;
          return flow;
        }
      }
    }
    return 0;
  }
public:
  Network(int N, int source, int sink) : source(source), sink(sink), level(N), index(N), G(N) {}
  void add_edge(int u, int v, int capacity) {
    G[u].push_back({v, 0, capacity, (int)G[v].size()});
    G[v].push_back({u, 0, 0, (int)G[u].size() - 1});
  }
  int max_flow() {
    int flow = 0;
    while (bfs()) {
      fill(index.begin(), index.end(), 0);
      while (int pushed = dfs(source, INF)) {
        flow += pushed;
      }
    }
    return flow;
  }
  vector<vector<int>> min_cut() {
    max_flow();
    vector<vector<int>> ans;
    for (int u = 0; u < (int)G.size(); ++u) {
      for (auto &e : G[u]) {
        if (e.capacity > 0 && level[u] != -1 && level[e.to] == -1) {
          ans.push_back({u, e.to});
        }
      }
    }
    return ans;
  }
  vector<vector<Edge>> get_graph() {
    return G;
  }

private:
  const int INF = numeric_limits<int>::max() / 2;
  int source, sink;
  vector<int> level, index;
  vector<vector<Edge>> G;
};

int main() {
  assert(freopen64("harta.in", "r", stdin));
  assert(freopen64("harta.out", "w", stdout));

  int N;
  cin >> N;
  vector<int> in(N), out(N);
  for (int i = 0; i < N; ++i) {
    cin >> out[i] >> in[i];
  }

  int sink = 2 * N, source = 2 * N + 1;
  Network network(2 * N + 2, source, sink);
  for (int u = 0; u < N; u++) {
    network.add_edge(source, u, out[u]);
    network.add_edge(N + u, sink, in[u]);
    for (int v = 0; v < N; v++) {
      if (u != v) {
        network.add_edge(u, v + N, 1);
      }
    }
  }

  cerr << network.max_flow() << "\n";

  auto graph = network.get_graph();
  vector<pair<int, int>> answer;
  for (int u = 0; u < N; u++) {
    for (auto &e : graph[u]) {
      if (e.flow == 1 && e.to != source && e.to != sink) {
        answer.push_back({u, e.to});
      }
    }
  }

  cout << answer.size() << "\n";
  for (const auto &[x, y] : answer) {
    cout << x + 1 << " " << y + 1 - N << "\n";
  }

  return 0;
}