Cod sursa(job #2589789)

Utilizator segtreapMihnea Andreescu segtreap Data 26 martie 2020 21:21:58
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

int helium[207][207];

class Dinic {
  struct Edge {
    int to, flow, next;
  };
  vector <Edge> edges;
  vector <int> adia, act, h;
  int S, D;

  bool bfs() {
    fill(h.begin(), h.end(), -1);
    h[S] = 0;
    vector <int> q = { S };

    for (int it = 0; it < (int)q.size(); it++) {
      int nod = q[it];
      for (int i = adia[nod]; i != -1; i = edges[i].next)
        if (h[edges[i].to] == -1 && edges[i].flow)
          h[edges[i].to] = 1 + h[nod], q.push_back(edges[i].to);
    }

    return h[D] != -1;
  }

  int dfs(int nod, int cap_max) {
    if (cap_max == 0 || nod == D)
      return cap_max;

    while (act[nod] != -1) {
      Edge& e = edges[act[nod]];
      int d;
      if (h[e.to] == 1 + h[nod] && (d = dfs(e.to, min(cap_max, e.flow))) != 0) {
        helium[nod][e.to] ^= 1;
        helium[e.to][nod] ^= 1;
        e.flow -= d;
        edges[act[nod] ^ 1].flow += d;
        return d;
      }
      act[nod] = edges[act[nod]].next;
    }
    return 0;
  }

public:

  void print() {
    int n = (D - 2) / 2;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (helium[i + 1][j + n + 1]) {
          printf("%d %d\n", i, j);
        }
      }
    }
  }

  Dinic(int n, int S, int D) : adia(n + 1, -1), h(n + 1), S(S), D(D) {}

  int flow() {
    int ans = 0, d;
    while (bfs()) {
      act = adia;
      while ((d = dfs(S, 1e9)) != 0)
        ans += d;
    }
    return ans;
  }

  void add_edge(int a, int b, int c) {
    edges.push_back({ b, c, (int)edges.size() });
    swap(edges.back().next, adia[a]);
    edges.push_back({ a, 0, (int)edges.size() });
    swap(edges.back().next, adia[b]);
  }
};

int main() {
  freopen ("harta.in", "r", stdin);
  freopen ("harta.out", "w", stdout);

  int n;
  scanf("%d", &n);
  Dinic d(2 * n + 2, 1, 2 * n + 2);
  for (int i = 1; i <= n; i++) {
    int out, in;
    scanf("%d %d", &out, &in);
    d.add_edge(1, i + 1, out);
    d.add_edge(i + n + 1, 2 * n + 2, in);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i != j) {
        d.add_edge(i + 1, j + n + 1, 1);
      }
    }
  }
  printf("%d\n", d.flow());
  d.print();
}