Cod sursa(job #3302466)

Utilizator IanisBelu Ianis Ianis Data 7 iulie 2025 23:08:44
Problema Taramul Nicaieri Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#define endl '\n'
#endif

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

template<typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }

template<typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }

constexpr int NMAX = 105;
constexpr int INF = 1e9+5;

struct FlowGraph {
   struct Node {
      int y, cap, rev;
   };

   const int S = 0, T = 1;

   vector<int> dist, idx;
   vector<vector<Node>> g;

   FlowGraph() {
      add_node();
      add_node();
   }

   int add_node() {
      dist.push_back(0);
      idx.push_back(0);
      g.emplace_back();
      return sz(g) - 1;
   }

   void add_edge(int x, int y, int cap) {
      g[x].emplace_back(y, cap, sz(g[y]));
      g[y].emplace_back(x, 0, sz(g[x]) - 1);
   }

   bool bfs() {
      fill(all(dist), INF);
      fill(all(idx), 0);

      queue<int> q;
      dist[S] = 0;
      q.push(S);

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

         for (auto &[ y, cap, _ ] : g[x]) {
            if (cap && ckmin(dist[y], dist[x] + 1)) {
               q.push(y);
            }
         }
      }

      return dist[T] != INF;
   }

   int dfs(const int x, const int flow = INF) {
      if (x == T) return flow;
      for (; idx[x] < sz(g[x]); idx[x]++) {
         auto &[ y, cap, rev ] = g[x][idx[x]];
         if (cap && dist[y] == dist[x] + 1) {
            if (const int f = dfs(y, min(flow, cap))) {
               cap -= f;
               g[y][rev].cap += f;
               return f;
            }
         }
      }
      return 0;
   }

   int compute() {
      int max_flow = 0;
      while (bfs()) {
         while (const int flow = dfs(S)) {
            max_flow += flow;
         }
      }
      return max_flow;
   }
};

int n;
int in[NMAX], out[NMAX];
vector<int> g[NMAX];
int l[NMAX], r[NMAX];
int val[NMAX];

void read() {
   cin >> n;
   for (int i = 1; i <= n; i++) {
      cin >> out[i] >> in[i];
   }
}

void solve() {
   FlowGraph f;
   int m = 0;
   for (int i = 1; i <= n; i++) {
      l[i] = f.add_node();
      r[i] = f.add_node();
      val[r[i]] = i;
      f.add_edge(f.S, l[i], out[i]);
      f.add_edge(r[i], f.T, in[i]);
      m += in[i];
   }

   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
         if (i != j) {
            f.add_edge(l[i], r[j], 1);
         }
      }
   }

   assert(f.compute() == m);

   cout << m << endl;
   for (int x = 1; x <= n; x++) {
      for (auto &[ y, cap, _] : f.g[l[x]]) {
         if (!cap && y != f.S) {
            cout << x << ' ' << val[y] << endl;
            out[x]--;
            in[val[y]]--;
         }
      }
   }

   for (int i = 1; i <= n; i++) {
      assert(in[i] == 0);
      assert(out[i] == 0);
   }
}

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

   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);

   read();
   solve();

   return 0;
}