test/yukicoder/1615.MCF.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/1615

Depends on

• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)
• ネットワーク単体法 (src/Optimization/NetworkSimplex.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1615
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// 重み付き二部マッチング(非想定解)
// 制約が厳しい
#include <iostream>
#include "src/Optimization/NetworkSimplex.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, M, K, L;
 cin >> N >> M >> K >> L;
 NetworkSimplex<int, long long, MAXIMIZE> graph;
 int gs= graph.add_vertex(), gt= graph.add_vertex();
 auto buyer= graph.add_vertices(N);
 auto product= graph.add_vertices(M);
 for (int i= 0; i < L; i++) {
  int X, Y, Z;
  cin >> X >> Y >> Z, X--, Y--;
  graph.add_edge(buyer[X], product[Y], 0, 1, (1ll << Z));
 }
 for (int i= 0; i < N; i++) graph.add_edge(gs, buyer[i], 0, 1, 0);
 for (int j= 0; j < M; j++) graph.add_edge(product[j], gt, 0, 1, 0);
 graph.add_edge(gs, gt, 0, N + M, 0);
 graph.add_supply(gs, N + M), graph.add_demand(gt, N + M);
 graph.b_flow();
 cout << graph.get_result_value() << '\n';
 return 0;
}

#line 1 "test/yukicoder/1615.MCF.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1615
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// 重み付き二部マッチング(非想定解)
// 制約が厳しい
#include <iostream>
#line 2 "src/Optimization/NetworkSimplex.hpp"
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <cstdint>
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 9 "src/Optimization/NetworkSimplex.hpp"
template <typename flow_t, typename cost_t, MinMaxEnum obj= MINIMIZE> class NetworkSimplex {
 struct Node {
  int par, pred;
  flow_t sup;
  cost_t pi;
 };
 struct Edge {
  int u, v;
  flow_t low, up, flow;
  cost_t cost;
  int8_t state= 1;
 };
 int n, m= 0;
 std::vector<Node> ns;
 std::vector<Edge> es;
 std::vector<int> bfs, next, prev;
 inline void link(int u, int v) { next[u]= v, prev[v]= u; }
 inline void link(int u, int v, int w) { link(u, v), link(v, w); }
 inline auto opp_cost(int e) const { return es[e].cost + ns[es[e].u].pi - ns[es[e].v].pi; }
 inline void pivot(int in_arc) {
  int u_in= es[in_arc].u, v_in= es[in_arc].v, u, e, a= u_in, b= v_in;
  while (a != b) a= ns[a].par == -1 ? v_in : ns[a].par, b= ns[b].par == -1 ? u_in : ns[b].par;
  if (es[in_arc].state == -1) std::swap(u_in, v_in);
  int lca= a, side= 0, u_out= -1, i= 0, S= 0;
  flow_t delta= es[in_arc].up;
  for (u= u_in; u != lca && delta > 0; u= ns[u].par) {
   flow_t d= u == es[e= ns[u].pred].v ? es[e].up - es[e].flow : es[e].flow;
   if (delta > d) delta= d, u_out= u, side= 1;
  }
  for (u= v_in; u != lca; u= ns[u].par) {
   flow_t d= u == es[e= ns[u].pred].u ? es[e].up - es[e].flow : es[e].flow;
   if (delta >= d) delta= d, u_out= u, side= -1;
  }
  if (delta > 0) {
   es[in_arc].flow+= delta*= es[in_arc].state;
   for (u= es[in_arc].u; u != lca; u= ns[u].par) es[e].flow+= u == es[e= ns[u].pred].u ? -delta : delta;
   for (u= es[in_arc].v; u != lca; u= ns[u].par) es[e].flow+= u == es[e= ns[u].pred].u ? delta : -delta;
  }
  if (side == 0) return es[in_arc].state*= -1, void();
  int out_arc= ns[u_out].pred, p;
  es[in_arc].state= 0, es[out_arc].state= es[out_arc].flow ? -1 : 1;
  if (side == -1) std::swap(u_in, v_in);
  for (u= u_in; u != u_out; u= ns[u].par) bfs[S++]= u;
  assert(S <= n);
  for (i= S; i--;) ns[p= ns[u].par].par= u= bfs[i], ns[p].pred= ns[u].pred, link(prev[p], next[p]), link(prev[u + n + 1], p, u + n + 1);
  link(prev[u_in], next[u_in]), link(prev[v_in + n + 1], u_in, v_in + n + 1);
  ns[u_in].par= v_in, ns[u_in].pred= in_arc;
  cost_t pi_delta= u_in == es[in_arc].u ? -opp_cost(in_arc) : opp_cost(in_arc);
  for (i= 0, S= 1, bfs[0]= u_in; i < S; i++) {
   ns[u= bfs[i]].pi+= pi_delta;
   for (int v= next[u + n + 1]; v != u + n + 1; v= next[v]) bfs[S++]= v;
  }
 }
 void calc() {
  cost_t inf_cost= 1;
  for (int e= 0; e < m; e++) es[e].flow= 0, es[e].state= 1, es[e].up-= es[e].low, ns[es[e].u].sup-= es[e].low, ns[es[e].v].sup+= es[e].low, inf_cost+= std::abs(es[e].cost);
  ns[n]= {-1, -1, 0, 0}, es.resize(m + n), bfs.resize(n + 1);
  next.resize(2 * n + 2), std::iota(next.begin() + n + 1, next.end(), n + 1);
  prev.resize(2 * n + 2), std::iota(prev.begin() + n + 1, prev.end(), n + 1);
  for (int u= 0, e= m; u < n; u++, e++) {
   ns[u].par= n, ns[u].pred= e, link(prev[n + n + 1], u, n + n + 1);
   if (auto supply= ns[u].sup; supply >= 0) {
    ns[u].pi= -inf_cost;
    es[e]= {u, n, 0, supply, supply, inf_cost, 0};
   } else {
    ns[u].pi= inf_cost;
    es[e]= {n, u, 0, -supply, -supply, inf_cost, 0};
   }
  }
  int block_size= std::max(int(std::ceil(std::sqrt(m + n))), std::min(10, n + 1));
  for (int e= 0, in_arc, cnt, seen;; pivot(in_arc)) {
   cost_t minimum= 0;
   for (in_arc= -1, cnt= block_size, seen= m + n; seen--; e= e + 1 == m + n ? 0 : e + 1) {
    if (minimum > es[e].state * opp_cost(e)) minimum= es[e].state * opp_cost(e), in_arc= e;
    if (--cnt == 0 && minimum < 0) break;
    if (cnt == 0) cnt= block_size;
   }
   if (in_arc == -1) break;
  }
  for (int e= 0; e < m; e++) es[e].flow+= es[e].low, es[e].up+= es[e].low, ns[es[e].u].sup+= es[e].low, ns[es[e].v].sup-= es[e].low;
 }
public:
 NetworkSimplex(int n= 0): n(n), ns(n + 1) {}
 int add_vertex() { return ns.resize(n + 2), n++; }
 std::vector<int> add_vertices(const int size) {
  std::vector<int> ret(size);
  std::iota(ret.begin(), ret.end(), n);
  return ns.resize((n+= size) + 1), ret;
 }
 class EdgePtr {
  friend class NetworkSimplex;
  const NetworkSimplex *instance;
  int e;
  EdgePtr(const NetworkSimplex *const instance, const int e): instance(instance), e(e) {}
  const Edge &edge() const { return instance->es[e]; }
 public:
  EdgePtr()= default;
  int src() const { return edge().u; }
  int dst() const { return edge().v; }
  flow_t flow() const { return edge().flow; }
  flow_t lower() const { return edge().low; }
  flow_t upper() const { return edge().up; }
  cost_t cost() const { return edge().cost; }
  cost_t gain() const { return -edge().cost; }
 };
 EdgePtr add_edge(int u, int v, flow_t low, flow_t up, cost_t cost) {
  assert(0 <= u && u < n && 0 <= v && v < n);
  es.push_back({u, v, low, up, 0, obj * cost});
  return EdgePtr{this, m++};
 }
 void add_supply(int u, flow_t supply) { ns[u].sup= supply; }
 void add_demand(int u, flow_t demand) { ns[u].sup= -demand; }
 auto get_supply(int u) const { return ns[u].sup; }
 auto get_potential(int u) const { return ns[u].pi; }
 template <typename cost_sum_t= cost_t> auto get_result_value() const {
  cost_sum_t sum= 0;
  for (int e= 0; e < m; e++) {
   sum+= es[e].flow * cost_sum_t(es[e].cost);
  }
  return sum * obj;
 }
 bool b_flow() {
  flow_t sum_supply= 0;
  for (int u= 0; u < n; u++) sum_supply+= ns[u].sup;
  if (sum_supply != 0) return false;
  calc();
  for (int e= m; e < m + n; e++)
   if (es[e].flow != 0) return es.resize(m), false;
  return es.resize(m), true;
 }
};
#line 8 "test/yukicoder/1615.MCF.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, M, K, L;
 cin >> N >> M >> K >> L;
 NetworkSimplex<int, long long, MAXIMIZE> graph;
 int gs= graph.add_vertex(), gt= graph.add_vertex();
 auto buyer= graph.add_vertices(N);
 auto product= graph.add_vertices(M);
 for (int i= 0; i < L; i++) {
  int X, Y, Z;
  cin >> X >> Y >> Z, X--, Y--;
  graph.add_edge(buyer[X], product[Y], 0, 1, (1ll << Z));
 }
 for (int i= 0; i < N; i++) graph.add_edge(gs, buyer[i], 0, 1, 0);
 for (int j= 0; j < M; j++) graph.add_edge(product[j], gt, 0, 1, 0);
 graph.add_edge(gs, gt, 0, N + M, 0);
 graph.add_supply(gs, N + M), graph.add_demand(gt, N + M);
 graph.b_flow();
 cout << graph.get_result_value() << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	extreme1.txt	AC	73 ms	10 MB
g++-13	extreme2.txt	AC	74 ms	9 MB
g++-13	extreme3.txt	AC	120 ms	11 MB
g++-13	extreme4.txt	AC	113 ms	11 MB
g++-13	extreme5.txt	AC	127 ms	12 MB
g++-13	extreme6.txt	AC	104 ms	11 MB
g++-13	extreme7.txt	AC	121 ms	11 MB
g++-13	extreme8.txt	AC	117 ms	11 MB
g++-13	extreme9.txt	AC	131 ms	11 MB
g++-13	killer_a1.txt	AC	156 ms	11 MB
g++-13	killer_a2.txt	AC	159 ms	11 MB
g++-13	killer_a3.txt	AC	154 ms	11 MB
g++-13	killer_a4.txt	AC	165 ms	12 MB
g++-13	killer_a5.txt	AC	187 ms	12 MB
g++-13	killer_a6.txt	AC	164 ms	11 MB
g++-13	killer_a7.txt	AC	220 ms	11 MB
g++-13	killer_a8.txt	AC	212 ms	12 MB
g++-13	killer_a9.txt	AC	215 ms	11 MB
g++-13	killer_b1.txt	AC	159 ms	11 MB
g++-13	killer_b2.txt	AC	164 ms	11 MB
g++-13	killer_b3.txt	AC	154 ms	11 MB
g++-13	killer_b4.txt	AC	149 ms	11 MB
g++-13	killer_b5.txt	AC	170 ms	12 MB
g++-13	killer_b6.txt	AC	161 ms	11 MB
g++-13	killer_b7.txt	AC	159 ms	11 MB
g++-13	killer_b8.txt	AC	176 ms	11 MB
g++-13	killer_b9.txt	AC	153 ms	11 MB
g++-13	large1.txt	AC	30 ms	5 MB
g++-13	large2.txt	AC	24 ms	5 MB
g++-13	large3.txt	AC	38 ms	6 MB
g++-13	large4.txt	AC	31 ms	6 MB
g++-13	large5.txt	AC	37 ms	6 MB
g++-13	large6.txt	AC	31 ms	6 MB
g++-13	large7.txt	AC	48 ms	6 MB
g++-13	large8.txt	AC	43 ms	8 MB
g++-13	large9.txt	AC	58 ms	6 MB
g++-13	middle1.txt	AC	6 ms	4 MB
g++-13	middle2.txt	AC	6 ms	4 MB
g++-13	middle3.txt	AC	6 ms	4 MB
g++-13	middle4.txt	AC	8 ms	4 MB
g++-13	middle5.txt	AC	6 ms	4 MB
g++-13	middle6.txt	AC	6 ms	4 MB
g++-13	middle7.txt	AC	8 ms	4 MB
g++-13	middle8.txt	AC	8 ms	4 MB
g++-13	middle9.txt	AC	8 ms	4 MB
g++-13	sample1.txt	AC	4 ms	4 MB
g++-13	sample2.txt	AC	4 ms	4 MB
g++-13	sample3.txt	AC	4 ms	4 MB
g++-13	small1.txt	AC	4 ms	4 MB
g++-13	small2.txt	AC	5 ms	4 MB
g++-13	small3.txt	AC	5 ms	4 MB
g++-13	small4.txt	AC	5 ms	4 MB
g++-13	small5.txt	AC	5 ms	4 MB
g++-13	small6.txt	AC	4 ms	4 MB
g++-13	small7.txt	AC	5 ms	4 MB
g++-13	small8.txt	AC	5 ms	4 MB
g++-13	small9.txt	AC	5 ms	4 MB
clang++-18	extreme1.txt	AC	72 ms	10 MB
clang++-18	extreme2.txt	AC	71 ms	10 MB
clang++-18	extreme3.txt	AC	120 ms	11 MB
clang++-18	extreme4.txt	AC	114 ms	11 MB
clang++-18	extreme5.txt	AC	129 ms	12 MB
clang++-18	extreme6.txt	AC	103 ms	11 MB
clang++-18	extreme7.txt	AC	123 ms	12 MB
clang++-18	extreme8.txt	AC	119 ms	11 MB
clang++-18	extreme9.txt	AC	133 ms	11 MB
clang++-18	killer_a1.txt	AC	156 ms	11 MB
clang++-18	killer_a2.txt	AC	159 ms	11 MB
clang++-18	killer_a3.txt	AC	156 ms	11 MB
clang++-18	killer_a4.txt	AC	165 ms	11 MB
clang++-18	killer_a5.txt	AC	187 ms	11 MB
clang++-18	killer_a6.txt	AC	165 ms	12 MB
clang++-18	killer_a7.txt	AC	221 ms	12 MB
clang++-18	killer_a8.txt	AC	213 ms	11 MB
clang++-18	killer_a9.txt	AC	214 ms	12 MB
clang++-18	killer_b1.txt	AC	159 ms	11 MB
clang++-18	killer_b2.txt	AC	164 ms	11 MB
clang++-18	killer_b3.txt	AC	156 ms	11 MB
clang++-18	killer_b4.txt	AC	150 ms	11 MB
clang++-18	killer_b5.txt	AC	172 ms	11 MB
clang++-18	killer_b6.txt	AC	162 ms	11 MB
clang++-18	killer_b7.txt	AC	160 ms	11 MB
clang++-18	killer_b8.txt	AC	178 ms	11 MB
clang++-18	killer_b9.txt	AC	155 ms	11 MB
clang++-18	large1.txt	AC	29 ms	5 MB
clang++-18	large2.txt	AC	23 ms	5 MB
clang++-18	large3.txt	AC	38 ms	6 MB
clang++-18	large4.txt	AC	32 ms	6 MB
clang++-18	large5.txt	AC	37 ms	6 MB
clang++-18	large6.txt	AC	31 ms	7 MB
clang++-18	large7.txt	AC	49 ms	6 MB
clang++-18	large8.txt	AC	45 ms	6 MB
clang++-18	large9.txt	AC	60 ms	8 MB
clang++-18	middle1.txt	AC	7 ms	4 MB
clang++-18	middle2.txt	AC	6 ms	4 MB
clang++-18	middle3.txt	AC	6 ms	4 MB
clang++-18	middle4.txt	AC	6 ms	4 MB
clang++-18	middle5.txt	AC	6 ms	4 MB
clang++-18	middle6.txt	AC	6 ms	4 MB
clang++-18	middle7.txt	AC	8 ms	4 MB
clang++-18	middle8.txt	AC	8 ms	4 MB
clang++-18	middle9.txt	AC	8 ms	4 MB
clang++-18	sample1.txt	AC	5 ms	4 MB
clang++-18	sample2.txt	AC	5 ms	4 MB
clang++-18	sample3.txt	AC	5 ms	4 MB
clang++-18	small1.txt	AC	5 ms	4 MB
clang++-18	small2.txt	AC	5 ms	4 MB
clang++-18	small3.txt	AC	5 ms	4 MB
clang++-18	small4.txt	AC	5 ms	4 MB
clang++-18	small5.txt	AC	5 ms	4 MB
clang++-18	small6.txt	AC	5 ms	4 MB
clang++-18	small7.txt	AC	5 ms	4 MB
clang++-18	small8.txt	AC	5 ms	4 MB
clang++-18	small9.txt	AC	5 ms	4 MB

Back to top page