Cod sursa(job #3262805)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 11 decembrie 2024 16:57:54
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <queue>

#define debug(x) #x << " = " << x << '\n';

using ll = long long;
#define int ll
const int INF = 1e18;

struct Dinic {
  struct Edge {
    int to, flow, cap;
  };
  
  int n;
  std::vector<Edge> e;
  std::vector<std::vector<int>> g;
  std::vector<int> dist;
  int source, sink;

  Dinic() {}
  Dinic(int _n) {
    n = _n;
    g.resize(n + 1);
    dist.resize(n + 1);
  }

  void add_edge(int u, int v, int cap) {
    e.push_back({v, 0, cap});
    e.push_back({u, 0, 0});
    g[u].push_back((int) e.size() - 2);
    g[v].push_back((int) e.size() - 1);
  }

  bool can_bfs() {
    std::queue<int> q;
    dist.assign(n + 1, INF);
    q.push(source);
    dist[source] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (const auto &ind : g[u]) {
        auto &[v, flow, cap] = e[ind];
        if (flow < cap &&  dist[u] + 1 < dist[v]) {
          dist[v] = 1 + dist[u];
          q.push(v);
        }
      }
    }
    return dist[sink] != INF;
  }

  int do_push(int u, int F) {
    if (u == sink) {
      return F;
    }
    int pushed = 0;
    for (const auto &ind : g[u]) {
      auto &[v, flow, cap] = e[ind];
      if (dist[u] + 1 == dist[v] && flow < cap) {
        int push = do_push(v, std::min(F, cap - flow));
        pushed += push;
        flow += push;
        e[ind ^ 1].flow -= push;
        F -= push;
      }
    }
    return pushed;
  } 

  int max_flow(int _source, int _sink) {
    source = _source;
    sink = _sink;
    int answer = 0;
    while (can_bfs()) {
      int push = do_push(source, INF);
      answer += push;
      if (push == 0) {
        break;
      }
    }
    return answer;
  }
};

signed main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #else
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
  #endif

  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n;
  std::cin >> n;

  std::vector<int> in(n + 1), out(n + 1);
  int m = 0;
  for (int i = 1; i <= n; i++) {
    std::cin >> in[i] >> out[i];
    m += in[i];
  }

  Dinic F(2 * n + 2);
  
  for (int i = 1; i <= n; i++) {
    F.add_edge(0, i, in[i]);
    F.add_edge(i + n, 2 * n + 1, out[i]);
  }
  
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i != j) {
        F.add_edge(i, j + n, 1);
      }
    }
  }
 
  std::cout << F.max_flow(0, 2 * n + 1) << '\n';

  int id = 4 * n - 2;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        id += 2;
        if (F.e[id].flow == 1) {
          std::cout << i + 1 << ' ' << j + 1 << '\n';
        }
      }
    }
  }
  return 0;
}