Cod sursa(job #2054412)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 1 noiembrie 2017 22:35:10
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;

#ifdef INFOARENA
#define ProblemName "harta"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 210;
vector<int> G[MAXN];
int N;

struct edge {
  int u, C;
  edge(int uu, int cc) : u(uu), C(cc) {}
};
vector<edge> edges;

inline void addEdge(int v, int u, int c) {
  G[v].push_back((int)edges.size());
  edges.push_back(edge(u, c));
  G[u].push_back((int)edges.size());
  edges.push_back(edge(v, 0));
}

int nedge[MAXN], dst[MAXN], Q[MAXN];
int _;
int ql, qr;
#define INFINIT 0x3F3F3F3F

bool BFS(int s) {
  memset(dst, 0x3F, sizeof(dst));
  dst[s] = 0;
  ql = 0, qr = 1;
  while ((ql < qr) && (dst[N - 1] == INFINIT)) {
    int t = Q[ql++];
    for (int i = 0; i != (int)G[t].size(); ++i) {
      int edgeID = G[t][i];
      int u = edges[edgeID].u;
      if (!edges[edgeID].C) continue;
      if (dst[u] != INFINIT) continue;
      dst[u] = dst[t] + 1;
      Q[qr++] = u;
    }
  }
  return (dst[N - 1] != INFINIT);
}

int DFS(int v, int flow) {
  if (v == (N - 1)) return flow;
  for (; nedge[v] != (int)G[v].size(); ++nedge[v]) {
    int edgeID = G[v][nedge[v]];
    int u = edges[edgeID].u;
    if (!edges[edgeID].C) continue;
    if (dst[v] + 1 != dst[u]) continue;
    int actualFlow = DFS(u, min(edges[edgeID].C, flow));
    if (actualFlow == 0) continue;
    edges[edgeID].C -= actualFlow;
    edges[edgeID ^ 1].C += actualFlow;
    return actualFlow;
  }
  return 0;
}

int blockingFlow() {
  int totalFlow = 0;
  memset(nedge, 0, sizeof(nedge));
  int flow = 0;
  while ((flow = DFS(0, INFINIT))) totalFlow += flow;
  return totalFlow;
}

int Dinic() {
  int flow = 0;
  while (BFS(0)) flow += blockingFlow();
  return flow;
}

void input() {
  int n;
  scanf("%d", &n);
  N = 2 * n + 2;
  for (int i = 0; i < n; ++i) {
    int inp, out;
    scanf("%d%d", &inp, &out);
    addEdge(0, 1 + i, inp);
    addEdge(1 + n + i, 2 * n + 1, out);
  }
  for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
  if (i != j)
    addEdge(1 + i, 1 + n + j, 1);
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  input();
  int f = Dinic();
  printf("%d\n", f);
  int n = (N - 2) / 2;
  for (int i = 1; i <= n; ++i)
  for (const auto &e : G[i]) {
    if (edges[e ^ 1].C == 0)
      continue;
    int j = edges[e].u - (1 + n);
    if (j < 0 || j >= n)
      continue;
    printf("%d %d\n", i, j + 1);
  }
  return 0;
}