Cod sursa(job #2233519)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 23 august 2018 15:46:44
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 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], daddy[MaxN];
 
inline void ClearQ() {
  while (Q.size()) {
    Q.pop();
  }
}
 
bool Bfs() {
  ClearQ();
  memset(daddy, Inf, sizeof daddy);
  daddy[Source] = -1;
  Q.push(Source);
 
  while (Q.size()) {
    int node = Q.front();
    Q.pop();
    if (node == Destination) {
      continue;
    }
 
    for (auto nxt: G[node]) {
      if (daddy[nxt] != Inf or !(Capacity[node][nxt] - Flow[node][nxt])) {
        continue;
      }
 
      Q.push(nxt);
      daddy[nxt] = node;
    }
  }
 
  return daddy[Destination] != Inf;
}
 
inline int CalcFlow(int node = Destination) {
  int ans = Inf;
  while (daddy[node] != -1) {
    int parent = daddy[node];
    ans = min(ans, Capacity[parent][node] - Flow[parent][node]);
    node = parent;
  }
 
  return ans;
}
 
inline void UpdateFlow(int Quantity, int node = Destination) {
  while (daddy[node] != -1) {
    int parent = daddy[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 daddy[nxt] == Inf) {
        continue;
      }
 
      daddy[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) {
      if (Flow[i][n + j] == 1) {
        cout << i << ' ' << j << '\n';
      }
    }
  }
 
  return 0;
}