Cod sursa(job #1830107)

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

using namespace std;

ifstream 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()) {
    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;
}