verify/AizuOnlineJudge/graph/flow/GRL_7_A_2.test.cpp

View this file on GitHub
Last update: 2026-05-03 14:51:15+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_7_A

Depends on

Code

#include "../../../../template/template.hpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_7_A"
#include "../../../../academic/MinimumCostB-flow.hpp"

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int x, y, e;
  int inf = 1e7;
  in(x, y, e);
  min_cost_flow<int, int> g(x + y + 2);
  g.add_edge(x + y + 1, x + y, 0, inf, -1);
  rep(i, x) g.add_edge(x + y, i, 0, 1, 0);
  rep(i, y) g.add_edge(x + i, x + y + 1, 0, 1, 0);

  rep(i, e) {
    int u, v;
    in(u, v);
    g.add_edge(u, x + v, 0, 1, 0);
  }
  vector<int> b(x + y + 2);
  out(-g.flow(b));
}

#line 2 "template/template.hpp"
#pragma region Macros
#include <bits/stdc++.h>
#include <tr2/dynamic_bitset>

using namespace std;
using namespace tr2;
using lint = long long;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128_t;
#define all(x) (x).begin(), (x).end()
#define uniqv(v) v.erase(unique(all(v)), v.end())
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define logfixed(x) cout << fixed << setprecision(10) << x << endl;

ostream &operator<<(ostream &dest, __int128_t value) {
  ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(ios_base::badbit);
    }
  }
  return dest;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 != (int)v.size() ? " " : "");
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &set_var) {
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << itr->first << " -> " << itr->second << "\n";
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const unordered_map<T, U> &map_var) {
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << itr->first << " -> " << itr->second << "\n";
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
  os << pair_var.first << " " << pair_var.second;
  return os;
}

void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
  cout << a;
  (cout << ... << (cout << ' ', b));
  cout << '\n';
}

void outf() { cout << '\n'; }
template <class T, class... Ts>
void outf(const T &a, const Ts &...b) {
  cout << fixed << setprecision(14) << a;
  (cout << ... << (cout << ' ', b));
  cout << '\n';
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &in : v) is >> in;
  return is;
}

inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First &first, Rest &...rest) {
  cin >> first;
  in(rest...);
  return;
}

template <typename T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

vector<lint> dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<lint> dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<lint> dx4 = {1, 0, -1, 0};
vector<lint> dy4 = {0, 1, 0, -1};

#pragma endregion
#line 2 "verify/AizuOnlineJudge/graph/flow/GRL_7_A_2.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_7_A"
#line 1 "academic/MinimumCostB-flow.hpp"
template <class Cap, class Cost>
class min_cost_flow {
 private:
  const Cost INF = numeric_limits<Cost>::max() / 4;
  struct Edge {
    int to;
    Cap cap, flow;
    Cost cost;
    int rev;
    bool is_rev;
  };

  vector<pair<int, int>> edge_id;
  vector<vector<Edge>> g;
  Cost base_cost = 0;
  int n;

 public:
  vector<Cost> p;
  min_cost_flow(int n) : n(n) {
    g.resize(n);
  }

  const Edge get_edge(int id) {
    auto [vid, eid] = edge_id[id];
    if (vid >= n) {
      int v = vid - n;
      return Edge{v, 0, eid, 0, 0, 0};
    }
    return g[vid][eid];
  }

  void edge_status() {
    for (int i = 0; i < n; i++) {
      for (auto [to, cap, flow, cost, rev, is_rev] : g[i]) {
        if (is_rev) continue;
        out(i, "->", to, " : ", flow);
      }
    }
  }

  void add_edge(int from, int to, Cap lower, Cap upper, Cost cost) {
    assert(lower <= upper);
    Cap x;
    if (cost >= 0) {
      x = lower;
    } else {
      x = upper;
    }

    int from_id = int(g[from].size());
    int to_id = int(g[to].size());
    if (from != to) {
      edge_id.emplace_back(from, from_id);
    } else {
      edge_id.emplace_back(n + from, x);
    }
    if (from != to) {
      g[from].push_back({to, upper, x, cost, to_id, false});
      g[to].push_back({from, upper - lower, upper - x, -cost, from_id, true});
    } else {
      base_cost += x * cost;
      return;
    }
  }

  Cost flow(vector<Cap> e) {
    for (int i = 0; i < n; i++) {
      for (auto const& edge : g[i]) {
        if (edge.is_rev) continue;
        int to = edge.to;
        Cap x = edge.flow;
        e[i] -= x;
        e[to] += x;
      }
    }
    vector<Cost> pot(n);
    vector<Cost> dist(n, INF);
    vector<int> prev_v(n, -1);
    vector<int> prev_e(n, -1);
    vector<bool> fin(n, false);
    while (1) {
      int s = -1;
      for (int i = 0; i < n; i++) {
        if (e[i] > 0) {
          s = i;
          break;
        }
      }

      if (s != -1) {
        fill(dist.begin(), dist.end(), INF);
        fill(prev_v.begin(), prev_v.end(), -1);
        fill(prev_e.begin(), prev_e.end(), -1);
        fill(fin.begin(), fin.end(), false);
        dist[s] = 0;

        priority_queue<pair<Cost, int>, vector<pair<Cost, int>>, greater<pair<Cost, int>>> q;
        q.emplace(0, s);
        while (!q.empty()) {
          auto [cur_d, cur] = q.top();
          q.pop();
          if (fin[cur]) continue;
          fin[cur] = true;
          for (int i = 0; i < int(g[cur].size()); i++) {
            const Edge& edge = g[cur][i];
            if (edge.cap - edge.flow <= 0) continue;
            Cost len = edge.cost - pot[cur] + pot[edge.to];
            if (!fin[edge.to] and dist[edge.to] > cur_d + len) {
              dist[edge.to] = cur_d + len;
              prev_v[edge.to] = cur;
              prev_e[edge.to] = i;
              q.emplace(dist[edge.to], edge.to);
            }
          }
        }

        int k = -1;
        for (int i = 0; i < n; i++) {
          if (e[i] < 0 and dist[i] != INF) {
            if (k == -1 or dist[i] < dist[k]) {
              k = i;
            }
          }
        }

        if (k != -1) {
          Cost D = dist[k];
          for (int i = 0; i < n; i++) {
            Cost delta = (dist[i] == INF ? D : min(dist[i], D));
            pot[i] -= delta;
          }
          Cap epsilon = min(e[s], -e[k]);
          int cur = k;
          while (cur != s) {
            int pv = prev_v[cur];
            int pe = prev_e[cur];
            const Edge& edge = g[pv][pe];
            Cap residual_cap = edge.cap - edge.flow;
            if (epsilon > residual_cap) epsilon = residual_cap;
            cur = pv;
          }

          cur = k;
          while (cur != s) {
            int pv = prev_v[cur];
            int pe = prev_e[cur];
            Edge& edge = g[pv][pe];
            edge.flow += epsilon;
            g[edge.to][edge.rev].flow -= epsilon;
            cur = prev_v[cur];
            cur = pv;
          }
          e[s] -= epsilon;
          e[k] += epsilon;
        } else {
          // 可能流が存在しない
          return numeric_limits<Cost>::max();
          break;
        }
      } else {
        break;
      }
    }

    p.resize(n);
    for (int i = 0; i < n; i++) {
      p[i] = -pot[i];
    }
    Cost z = base_cost;
    for (int i = 0; i < n; i++) {
      for (auto const& edge : g[i]) {
        if (edge.is_rev) continue;
        z += edge.flow * edge.cost;
      }
    }
    return z;
  }
};
#line 4 "verify/AizuOnlineJudge/graph/flow/GRL_7_A_2.test.cpp"

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int x, y, e;
  int inf = 1e7;
  in(x, y, e);
  min_cost_flow<int, int> g(x + y + 2);
  g.add_edge(x + y + 1, x + y, 0, inf, -1);
  rep(i, x) g.add_edge(x + y, i, 0, 1, 0);
  rep(i, y) g.add_edge(x + i, x + y + 1, 0, 1, 0);

  rep(i, e) {
    int u, v;
    in(u, v);
    g.add_edge(u, x + v, 0, 1, 0);
  }
  vector<int> b(x + y + 2);
  out(-g.flow(b));
}