Cod sursa(job #1830110)

Utilizator BrandonChris Luntraru Brandon Data 16 decembrie 2016 10:30:41
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

class InputReader {
public:
  InputReader() {}
  InputReader(const char *file_name) {
    input_file = fopen(file_name, "r");
    cursor = 0;
    fread(buffer, SIZE, 1, input_file);
  }
  inline InputReader &operator >>(int &n) {
    while (buffer[cursor] < '0' || buffer[cursor] > '9') {
      advance();
    }
    n = 0;
    while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
      n = n * 10 + buffer[cursor] - '0';
      advance();
    }
    return *this;
  }
private:
  FILE *input_file;
  static const int SIZE = 1 << 17;
  int cursor;
  char buffer[SIZE];
  inline void advance() {
    ++ cursor;
    if (cursor == SIZE) {
      cursor = 0;
      fread(buffer, SIZE, 1, input_file);
    }
  }
};

InputReader cin ("harta.in");
ofstream cout ("harta.out");

const int MaxN = 205, Inf = 0x3f3f3f3f;

vector <int> G[MaxN];
queue <int> Q;
int n, m, Source, Destination;
int Capacity[MaxN][MaxN], Flow[MaxN][MaxN], Distance[MaxN], father[MaxN];

inline void ClearQ() {
  while (Q.size()) {
    Q.pop();
  }
}

bool Bfs() {
  ClearQ();
  memset(father, 0, sizeof father);
  memset(Distance, 0, sizeof Distance);
  father[Source] = -1;
  Q.push(Source);

  while (Q.size()) {
    int node = Q.front();
    Q.pop();

    for (auto nxt: G[node]) {
      if (father[nxt] or !(Capacity[node][nxt] - Flow[node][nxt])) {
        continue;
      }

      Q.push(nxt);
      Distance[nxt] = Distance[node] + 1;
      father[nxt] = node;

      if (nxt == Destination) {
        return true;
      }
    }
  }

  return false;
}

inline void UpdateFlow(int Quantity, int node = Destination) {
  while (father[node] != -1) {
    int parent = father[node];
    Flow[parent][node] += Quantity;
    Flow[node][parent] -= Quantity;
    node = parent;
  }
}

int main() {
  cin >> n;
  Source = 0;
  Destination = 2 * n + 1;
  for (int i = 1; i <= n; ++i) {
    int a, b;
    cin >> a >> b;
    m += a;

    G[Source].push_back(i);
    G[i].push_back(Source);
    Capacity[Source][i] = a;

    G[n + i].push_back(Destination);
    G[Destination].push_back(n + i);
    Capacity[n + i][Destination] = b;
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (i == j) {
        continue;
      }

      G[i].push_back(n + j);
      G[n + j].push_back(i);
      Capacity[i][n + j] = 1;
    }
  }


  while (Bfs()) {
    for (auto nxt: G[Destination]) {
      if (Capacity[nxt][Destination] - Flow[nxt][Destination] and father[nxt]) {
        father[Destination] = nxt;
        UpdateFlow(1);
      }
    }
  }

  cout << m << '\n';
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      //cout << "[" << i << "][" << j << "] = " << Flow[i][n + j] << '\n';
      if (Flow[i][n + j] == 1) {
        cout << i << ' ' << j << '\n';
      }
    }
  }

  return 0;
}