Cod sursa(job #3193600)

Utilizator ZahaZaharie Stefan Zaha Data 15 ianuarie 2024 00:39:05
Problema Taramul Nicaieri Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <fstream>
#include <utility>
#include <vector>

class Graph {
  const int n, src, dest, max_size;
  std::vector<std::vector<int>> adj, flow, cap;
  std::vector<int> s, t;
  std::vector<bool> visited;

  void init(std::vector<std::pair<int, int>> roads) {
    for (int i = 1; i <= n; ++i) {
      int in = roads[i - 1].second, out = roads[i - 1].first;
      adj[src].emplace_back(i);
      adj[i].emplace_back(src);
      cap[src][i] = out;
      adj[n + i].emplace_back(dest);
      adj[dest].emplace_back(n + i);
      cap[n + i][dest] = in;
    }

    for (int i = 1; i <= n; ++i) {
      for (int j = n + 1; j <= 2 * n; ++j) {
        if (j != n + i) {
          adj[i].emplace_back(j);
          adj[j].emplace_back(i);
          cap[i][j] = 1;
        }
      }
    }
  }

  bool bfs() {
    visited.assign(max_size, false);
    visited[src] = true;

    int start = 1, end = 1;
    s[src] = 0;
    t[src] = -1;

    while (start <= end) {
      int curr = s[start++];
      for (int i = 0; i < adj[curr].size(); ++i) {
        int next = adj[curr][i];
        if (!visited[next] && cap[curr][next] - flow[curr][next] > 0) {
          visited[next] = true;
          s[++end] = next;
          t[next] = curr;
          if (next == dest) {
            return true;
          }
        }
      }
    }

    return false;
  }

public:
  Graph(int n, std::vector<std::pair<int, int>> roads)
      : n{n}, src{0}, dest{2 * n + 1}, max_size{2 * n + 2} {
    adj.assign(max_size, std::vector<int>());
    flow.assign(max_size, std::vector<int>(max_size, 0));
    cap.assign(max_size, std::vector<int>(max_size, 0));
    s.assign(max_size, 0);
    t.assign(max_size, 0);

    init(roads);
  }

  std::vector<std::pair<int, int>> get_ans() {
    while (bfs()) {
      for (int i = 0; i < adj[dest].size(); ++i) {
        int next = adj[dest][i];
        if (visited[next] && flow[next][dest] < cap[next][dest]) {
          int min = cap[next][dest] - flow[next][dest];

          int curr = next;
          while (t[curr] != -1) {
            min = std::min(min, cap[t[curr]][curr] - flow[t[curr]][curr]);
            curr = t[curr];
          }

          flow[next][dest] += min;
          flow[dest][next] -= min;

          curr = next;
          while (t[curr] != -1) {
            flow[t[curr]][curr] += min;
            flow[curr][t[curr]] -= min;
            curr = t[curr];
          }
        }
      }
    }

    std::vector<std::pair<int, int>> ans;
    for (int i = 1; i <= n; ++i) {
      for (int j = n + 1; j <= 2 * n; ++j) {
        if (flow[i][j] == 1) {
          ans.emplace_back(std::make_pair(i, j - n));
        }
      }
    }
    return ans;
  }
};

int main() {
  std::ifstream fin("harta.in");
  std::ofstream fout("harta.out");

  int n;
  fin >> n;

  std::vector<std::pair<int, int>> roads;
  for (int i = 0; i < n; ++i) {
    int in, out;
    fin >> out >> in;
    roads.emplace_back(std::make_pair(out, in));
  }

  Graph g(n, roads);
  std::vector<std::pair<int, int>> ans = g.get_ans();

  fout << ans.size() << "\n";
  for (auto it : ans) {
    fout << it.first << " " << it.second << "\n";
  }

  fin.close();
  fout.close();
  return 0;
}