Cod sursa(job #2589781)

Utilizator segtreapMihnea Andreescu segtreap Data 26 martie 2020 20:57:12
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>
#include <queue>

using namespace std;

const int N = 300 + 7;
vector<int> g[N];
int s;
int d;
int l[N];

struct Edge {
  int to;
  int cost;
};

vector<Edge> edges;

void add(int a, int b, int c) {
  g[a].push_back((int) edges.size());
  edges.push_back({b, c});
  g[b].push_back((int) edges.size());
  edges.push_back({a, c});
}

bool bfs() {
  queue<int> q;
  for (int i = 1; i <= d; i++) {
    l[i] = -1;
  }
  l[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int a = q.front();
    q.pop();
    for (auto &i : g[a]) {
      int b = edges[i].to;
      if (edges[i].cost > 0 && l[b] == -1) {
        l[b] = 1 + l[a];
        q.push(b);
      }
    }
  }
  return l[d] != -1;
}

int dfs(int a, int cap) {
  if (a == d || cap == 0) {
    return cap;
  }
  for (auto &i : g[a]) {
    int b = edges[i].to;
    int co = edges[i].cost;
    if (co > 0 && l[b] == 1 + l[a]) {
      int val = dfs(b, min(cap, co));
      if (val > 0) {
        edges[i].cost -= val;
        edges[i ^ 1].cost += val;
        return val;
      }
    }
  }
  return 0;
}

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

  int n;
  scanf("%d", &n);
  s = 1;
  d = 2 * n + 2;
  for (int i = 1; i <= n; i++) {
    int out, in;
    scanf("%d %d", &out, &in);
    add(s, i + 1, in);
    add(i + n + 1, d, out);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i != j) {
        add(i + 1, j + n + 1, 1);
      }
    }
  }
  while (bfs()) {
    while (dfs(s, (int) 1e9)) {
    }
  }
  vector<pair<int, int>> sol;
  for (int i = 1; i <= n; i++) {
    for (auto &id : g[i + 1]) {
      int j = edges[id].to - n - 1;
      int co = edges[id].cost;
      if (co == 0 && 1 <= j && j <= n) {
        sol.push_back({i, j});
      }
    }
  }
  printf("%d\n", (int) sol.size());
  for (auto &it : sol) {
    printf("%d %d\n", it.first, it.second);
  }
}