Cod sursa(job #2434359)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 1 iulie 2019 16:38:20
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

struct MaxFlow {
  int n, source, sink, flow;
  vector<int> parent;
  vector<vector<int>> adj, capacity;
  MaxFlow(int n_, int source_, int sink_) : 
    n(n_), source(source_), sink(sink_), flow(0), parent(n), adj(n), 
      capacity(n, vector<int>(n)) {}
  void AddEdge(int u, int v, int cap) {
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
    capacity[u][v] += cap;
  }
  bool CanIncreaseFlow() {
    fill(parent.begin(), parent.end(), -1);
    parent[source] = -2;
    vector<int> q = {source};
    for (int i = 0; i < (int)q.size(); ++i) {
      int node = q[i];
      for (int &x : adj[node]) {
        if (parent[x] == -1 && capacity[node][x]) {
          parent[x] = node;
          q.emplace_back(x);
        }
      }
    }
    return parent[sink] != -1;
  }
  int GetMaxFlow() {
    while (CanIncreaseFlow()) {
      int node = sink;
      int add_flow = (int)1e9;
      while (node != source) {
        add_flow = min(add_flow, capacity[parent[node]][node]);
        node = parent[node];
      }
      node = sink;
      while (node != source) {
        capacity[parent[node]][node] -= add_flow;
        capacity[node][parent[node]] += add_flow;
        node = parent[node];
      }
      flow += add_flow;
    }
    return flow;
  }
};

int main() {
  ifstream cin("harta.in");
  ofstream cout("harta.out");

  int n; cin >> n;
  MaxFlow g(2 * n + 2, 0, 2 * n + 1);
  for (int i = 1; i <= n; ++i) {
    int in, out; cin >> in >> out;
    g.AddEdge(g.source, i, in);
    g.AddEdge(i + n, g.sink, out);
    for (int j = 1; j <= n; ++j) if (i != j) {
      g.AddEdge(i, j + n, 1);
    }
  }
  cout << g.GetMaxFlow() << endl;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) if (i != j) {
      if (g.capacity[i][j + n] == 0) {
        cout << i << ' ' << j << '\n';
      }
    }
  }
}