Cod sursa(job #2774716)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 12 septembrie 2021 15:04:37
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

struct flow_edge {
  int u, v, cap;

  flow_edge(int _u, int _v, int _cap) : u(_u), v(_v), cap(_cap) {}
};

struct Dinic {
  int n, m = 0, s, t;
  vector<flow_edge> edges;
  vector<vector<int>> adj;
  vector<int> level, ptr;
  queue<int> q;

  Dinic(int N, int source, int sink) : n(N), s(source), t(sink) {
    adj.resize(n + 1);
    level.resize(n + 1);
    ptr.resize(n + 1);
  }

  void add_edge(int u, int v, int cap) {
    edges.emplace_back(u, v, cap);
    adj[u].emplace_back(m++);
    edges.emplace_back(v, u, 0);
    adj[v].emplace_back(m++);
  }

  bool bfs() {
    while (!q.empty()) {
      int curr = q.front();
      q.pop();
      for (int id : adj[curr])
        if (level[edges[id].v] == -1 && edges[id].cap) {
          level[edges[id].v] = level[curr] + 1;
          q.emplace(edges[id].v);
        }
    }
    return level[t] != -1;
  }

  int dfs(int u, int curr_flow) {
    if (curr_flow == 0)
      return 0;
    if (u == t)
      return curr_flow;
    for (int& p = ptr[u]; p < static_cast<int>(adj[u].size()); ++p) {
      int id = adj[u][p];
      int v = edges[id].v;
      if (level[u] + 1 != level[v] || edges[id].cap <= 0)
        continue;
      int new_flow = dfs(v, min(curr_flow, edges[id].cap));
      if (new_flow == 0)
        continue;
      edges[id].cap -= new_flow;
      edges[id ^ 1].cap += new_flow;
      return new_flow;
    }
    return 0;
  }

  int max_flow() {
    int flow = 0;
    while (true) {
      fill(level.begin(), level.end(), -1);
      level[s] = 0;
      q.emplace(s);
      if (!bfs())
        break;
      fill(ptr.begin(), ptr.end(), 0);
      while (int curr_flow = dfs(s, INF))
        flow += curr_flow;
    }
    return flow;
  }

  void print_edges(int N) {
    for (const auto &it : edges)
      if (it.cap == 0 && 1 <= it.u && it.u <= N && N < it.v && it.v <= (N << 1))
        fout << it.u << ' ' << it.v - N << '\n';
  }
};

int main() {
  int n;
  fin >> n;
  int m = n << 1 | 1;
  Dinic g(m, 0, m);
  for (int i = 1; i <= n; ++i) {
    int x, y;
    fin >> x >> y;
    g.add_edge(0, i, x);
    g.add_edge(i + n, m, y);
    for (int j = 1; j <= n; ++j)
      if (i != j)
        g.add_edge(i, j + n, 1);
  }
  fout << g.max_flow() << '\n';
  g.print_edges(n);
  fin.close();
  fout.close();
  return 0;
}