Cod sursa(job #1830139)

Utilizator BrandonChris Luntraru Brandon Data 16 decembrie 2016 11:27:17
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.3 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], father[MaxN];
bool used[MaxN];

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

bool Bfs() {
  //ClearQ();
  //memset(father, Inf, sizeof father);
  memset(used, false, sizeof used);
  father[Source] = -1;
  used[Source] = true;
  Q.push(Source);

  while (Q.size()) {
    int node = Q.front();
    Q.pop();
    if (node == Destination) {
      continue;
    }

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

      Q.push(nxt);
      father[nxt] = node;
      used[nxt] = true;
    }
  }

  return used[Destination];
}

inline int CalcFlow(int node = Destination) {
  int ans = Inf;
  while (father[node] != -1) {
    int parent = father[node];
    ans = min(ans, Capacity[parent][node] - Flow[parent][node]);
    node = parent;
  }

  return ans;
}

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]) or !used[nxt]) {
        continue;
      }

      father[Destination] = nxt;
      int Quantity = CalcFlow();
      if (Quantity) {
        UpdateFlow(Quantity);
      }
    }
  }

  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;
}