Cod sursa(job #3262791)

Utilizator IanisBelu Ianis Ianis Data 11 decembrie 2024 16:32:39
Problema Taramul Nicaieri Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#pragma GCC optimize("Ofast")
#ifndef LOCAL
#include <bits/stdc++.h>
#define endl '\n'
#else
#include <iostream>
#endif

using namespace std;

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

const int NMAX = 105;
const int INF = 2e9+5;

struct Dinic {
   struct Edge {
      int x, cap, other;
   };

   int n;
   vector<vector<Edge>> e;
   vector<int> dist, last;
   int S, T;

   Dinic() {
      S = add_node();
      T = add_node();
   }

   int add_node() {
      e.emplace_back();
      dist.emplace_back();
      last.emplace_back();
      return sz(e) - 1;
   }

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

   bool bfs() {
      fill(all(dist), INF);
      fill(all(last), 0);
      queue<int> q;
      q.push(S);
      dist[S] = 0;

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

         for (auto &[ u, cap, _ ] : e[x]) {
            if (cap && dist[u] == INF) {
               dist[u] = dist[x] + 1;
               q.push(u);
            }
         }
      }

      return dist[T] != INF;
   }

   int dfs(int x, int flow = INF) {
      if (flow == 0) return 0;
      if (x == T) return flow;

      for (; last[x] < sz(e[x]); last[x]++) {
         int i = last[x];
         auto &it = e[x][i];
         if (it.cap && dist[it.x] == dist[x] + 1) {
            if (int f = dfs(it.x, min(flow, it.cap))) {
               it.cap -= f;
               e[it.x][it.other].cap += f;
               return f;
            }
         }
      }

      return 0;
   }

   int max_flow() {
      int flow = 0;

      while (bfs()) {
         while (int f = dfs(S)) {
            flow += f;
         }
      }

      return flow;
   }
};

int n, m;
int out[NMAX], in[NMAX];
int a[NMAX], b[NMAX];
int bval[NMAX];

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

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(0);
   cout.tie(0);

   read();

   Dinic d;

   for (int i = 1; i <= n; i++) {
      a[i] = d.add_node();
      d.add_edge(d.S, a[i], out[i]);
      b[i] = d.add_node();
      bval[b[i]] = i;
      d.add_edge(b[i], d.T, in[i]);
   }

   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
         if (i != j) {
            d.add_edge(a[i], b[j], 1);
         }
      }
   }

   cout << d.max_flow() << endl;
   for (int i = 1; i <= n; i++) {
      for (auto &[ j, cap, _ ] : d.e[a[i]]) {
         if (j != d.S && cap == 0) {
            cout << i << ' ' << bval[j] << endl;
         }
      }
   }
   
   return 0;
}