test/aoj/GRL_2_B.weighted_matroid_intersection.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 11:17:48+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_B

Depends on

• マトロイド交叉 (src/Optimization/matroid_intersection.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_B
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// 重み付き
// 最小全域有向木(グラフ+分割)
#include <iostream>
#include <vector>
#include "src/Optimization/matroid_intersection.hpp"
using namespace std;
int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, M, r;
 cin >> N >> M >> r;
 GraphicMatroid M1(N);
 vector<int> w(M);
 vector<vector<int>> parts(N);
 for (int i= 0; i < M; i++) {
  int s, t;
  cin >> s >> t >> w[i];
  M1.add_edge(s, t);
  parts[t].push_back(i);
 }
 vector<int> R(N, 1);
 R[r]= 0;
 PartitionMatroid M2(M, parts, R);
 auto S= weighted_matroid_intersection<MINIMIZE>(M, M1, M2, w);
 int ans= 0;
 for (int e: S[N - 1]) ans+= w[e];
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/GRL_2_B.weighted_matroid_intersection.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_B
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// 重み付き
// 最小全域有向木(グラフ+分割)
#include <iostream>
#include <vector>
#line 3 "src/Optimization/matroid_intersection.hpp"
#include <algorithm>
#include <limits>
#include <array>
#include <queue>
#include <cassert>
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 9 "src/Optimization/matroid_intersection.hpp"
template <typename Matroid1, typename Matroid2> std::vector<int> matroid_intersection(int n, Matroid1 M1, Matroid2 M2) {
 std::vector<int> b(n, false), pre(n), I[2];
 for (int e= 0; e < n; e++) I[0].push_back(e);
 M1.build(I[1]), M2.build(I[1]);
 for (bool converged= false; !converged;) {
  pre.assign(n, false);
  std::vector L(1, std::vector<int>());
  for (int u: I[0])
   if (M1.oracle(u)) pre[u]= true, L[0].push_back(u);
  int m= 0;
  for (; L.back().size(); m+= 2) {
   L.push_back({});
   for (int e: L[m]) {
    if (converged= M2.oracle(e)) break;
    for (int f: I[1])
     if (!pre[f] && M2.oracle(f, e)) L[m + 1].push_back(f), pre[f]= true;
   }
   if (converged) break;
   L.push_back({});
   for (int e: L[m + 1])
    for (int f: I[0])
     if (!pre[f] && M1.oracle(e, f)) L[m + 2].push_back(f), pre[f]= true;
  }
  if (!converged) break;
  std::vector<std::vector<int>> L2(m + 1);
  for (int e: L[m])
   if (M2.oracle(e)) L2[m].push_back(e);
  for (int i= m; i; i-= 2) {
   for (int e: L[i - 1])
    for (int f: L2[i])
     if (M1.oracle(e, f)) {
      L2[i - 1].push_back(e);
      break;
     }
   for (int e: L[i - 2])
    for (int f: L2[i - 1])
     if (M2.oracle(f, e)) {
      L2[i - 2].push_back(e);
      break;
     }
  }
  pre.assign(n, -1);
  for (int e: L2[0])
   if (M1.oracle(e)) {
    bool isok= false;
    if (m) {
     std::vector<size_t> ei(m);
     for (int i= 0; e != -1;) {
      if (ei[i] == L2[i + 1].size()) e= pre[e], ei[i--]= 0;
      else if (int f= L2[i + 1][ei[i]++]; pre[f] == -1 && (i & 1 ? M1.oracle(e, f) : M2.oracle(f, e)))
       if (pre[f]= e, e= f; ++i == m) {
        if (M2.oracle(e))
         for (isok= true; e != -1; e= pre[e]) b[e]= !b[e];
        else e= pre[e], --i;
       }
     }
    } else if (M2.oracle(e)) isok= true, b[e]= 1;
    if (isok) {
     converged= false, I[0].clear(), I[1].clear();
     for (int u= 0; u < n; u++) I[b[u]].push_back(u);
     M1.build(I[1]), M2.build(I[1]);
    }
   }
 }
 return I[1];
}
template <MinMaxEnum sgn, class Matroid1, class Matroid2, class cost_t> std::vector<std::vector<int>> weighted_matroid_intersection(int n, Matroid1 M1, Matroid2 M2, std::vector<cost_t> c) {
 assert(n == (int)c.size());
 bool b[n];
 std::fill_n(b, n, false);
 std::vector<int> I[2], p;
 std::vector<std::vector<int>> ret(1);
 for (int u= 0; u < n; u++) I[0].push_back(u);
 if constexpr (sgn == MAXIMIZE) {
  auto cmx= *std::max_element(c.begin(), c.end());
  for (auto &x: c) x-= cmx;
 } else {
  auto cmi= *std::min_element(c.begin(), c.end());
  for (auto &x: c) x-= cmi;
 }
 for (auto &x: c) x*= -sgn * (n + 1);
 for (bool converged= false; !converged;) {
  converged= true, M1.build(I[1]), M2.build(I[1]);
  std::priority_queue<std::pair<cost_t, int>> pq;
  std::vector<cost_t> dist(n, std::numeric_limits<cost_t>::lowest());
  for (int u: I[0])
   if (M1.oracle(u)) pq.emplace(dist[u]= c[u] - 1, u);
  for (p.assign(n, -1); pq.size();) {
   auto [d, u]= pq.top();
   if (pq.pop(); d != dist[u]) continue;
   if (b[u]) {
    for (int v: I[0])
     if (M1.oracle(u, v))
      if (cost_t cost= d + c[v] - 1; dist[v] < cost) pq.emplace(dist[v]= cost, v), p[v]= u;
   } else {
    if (M2.oracle(u)) {
     for (int v= u; v != -1; v= p[v]) b[v]= !b[v];
     I[0].clear(), I[1].clear(), converged= false;
     for (int u= 0; u < n; u++) I[b[u]].push_back(u);
     ret.emplace_back(I[1]);
     break;
    }
    for (int v: I[1])
     if (M2.oracle(v, u))
      if (cost_t cost= d - c[v] - 1; dist[v] < cost) pq.emplace(dist[v]= cost, v), p[v]= u;
   }
  }
 }
 return ret;
}
class GraphicMatroid {
 int n;
 std::vector<std::array<int, 2>> es;
 std::vector<int> g, pos, comp, in, out;
 inline bool is_ancestor(int u, int v) const { return in[u] <= in[v] && in[v] < out[u]; }
public:
 GraphicMatroid(int n_): n(n_), comp(n), in(n), out(n) {}
 int add_edge(int u, int v) { return es.push_back({u, v}), es.size() - 1; }
 void build(const std::vector<int> &I) {
  in.assign(n, -1), g.resize(I.size() * 2), pos.assign(n + 1, 0);
  for (int e: I) {
   auto [u, v]= es[e];
   ++pos[u], ++pos[v];
  }
  for (int i= 0; i < n; ++i) pos[i + 1]+= pos[i];
  for (int e: I) {
   auto [u, v]= es[e];
   g[--pos[u]]= v, g[--pos[v]]= u;
  }
  std::vector<int> ei(pos.begin(), pos.begin() + n), pre(n, -1);
  for (int u= 0, t= 0, p; u < n; u++)
   if (in[u] == -1)
    for (in [comp[u]= p= u]= t++; p >= 0;) {
     if (ei[p] == pos[p + 1]) out[p]= t, p= pre[p];
     else if (int v= g[ei[p]++]; in[v] == -1) comp[v]= comp[u], pre[v]= p, in[p= v]= t++;
    }
 }
 inline bool oracle(int e) const { return comp[es[e][0]] != comp[es[e][1]]; }
 inline bool oracle(int e, int f) const {
  if (oracle(f)) return true;
  return e= es[e][in[es[e][0]] < in[es[e][1]]], is_ancestor(e, es[f][0]) != is_ancestor(e, es[f][1]);
 }
};
struct PartitionMatroid {
 std::vector<int> belong, R, cnt;
 PartitionMatroid(int m_, const std::vector<std::vector<int>> &parts, const std::vector<int> &R_): belong(m_, -1), R(R_) {
  assert(parts.size() == R.size());
  for (int i= parts.size(); i--;)
   for (int e: parts[i]) belong[e]= i;
 }
 void build(const std::vector<int> &I) {
  cnt= R;
  for (int e: I)
   if (belong[e] != -1) cnt[belong[e]]--;
 }
 inline bool oracle(int e) const { return belong[e] == -1 || cnt[belong[e]] > 0; }
 inline bool oracle(int e, int f) const { return oracle(f) || belong[e] == belong[f]; }
};
#line 9 "test/aoj/GRL_2_B.weighted_matroid_intersection.test.cpp"
using namespace std;
int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, M, r;
 cin >> N >> M >> r;
 GraphicMatroid M1(N);
 vector<int> w(M);
 vector<vector<int>> parts(N);
 for (int i= 0; i < M; i++) {
  int s, t;
  cin >> s >> t >> w[i];
  M1.add_edge(s, t);
  parts[t].push_back(i);
 }
 vector<int> R(N, 1);
 R[r]= 0;
 PartitionMatroid M2(M, parts, R);
 auto S= weighted_matroid_intersection<MINIMIZE>(M, M1, M2, w);
 int ans= 0;
 for (int e: S[N - 1]) ans+= w[e];
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	5 ms	4 MB
g++-13	00_sample_01.in	AC	4 ms	4 MB
g++-13	critical1.in	AC	4 ms	4 MB
g++-13	critical2.in	AC	5 ms	4 MB
g++-13	critical3.in	AC	4 ms	4 MB
g++-13	critical4.in	AC	4 ms	4 MB
g++-13	critical5.in	AC	4 ms	4 MB
g++-13	critical6.in	AC	4 ms	3 MB
g++-13	critical7.in	AC	4 ms	4 MB
g++-13	critical8.in	AC	4 ms	4 MB
g++-13	out1.in	AC	4 ms	4 MB
g++-13	out10.in	AC	17 ms	4 MB
g++-13	out11.in	AC	16 ms	4 MB
g++-13	out12.in	AC	16 ms	4 MB
g++-13	out13.in	AC	19 ms	4 MB
g++-13	out14.in	AC	15 ms	4 MB
g++-13	out15.in	AC	16 ms	4 MB
g++-13	out2.in	AC	4 ms	4 MB
g++-13	out3.in	AC	4 ms	4 MB
g++-13	out4.in	AC	4 ms	4 MB
g++-13	out5.in	AC	4 ms	4 MB
g++-13	out6.in	AC	20 ms	4 MB
g++-13	out7.in	AC	18 ms	4 MB
g++-13	out8.in	AC	18 ms	4 MB
g++-13	out9.in	AC	17 ms	4 MB
clang++-18	00_sample_00.in	AC	5 ms	4 MB
clang++-18	00_sample_01.in	AC	4 ms	4 MB
clang++-18	critical1.in	AC	4 ms	4 MB
clang++-18	critical2.in	AC	4 ms	4 MB
clang++-18	critical3.in	AC	4 ms	4 MB
clang++-18	critical4.in	AC	4 ms	4 MB
clang++-18	critical5.in	AC	4 ms	4 MB
clang++-18	critical6.in	AC	4 ms	4 MB
clang++-18	critical7.in	AC	4 ms	4 MB
clang++-18	critical8.in	AC	4 ms	4 MB
clang++-18	out1.in	AC	4 ms	4 MB
clang++-18	out10.in	AC	17 ms	4 MB
clang++-18	out11.in	AC	16 ms	4 MB
clang++-18	out12.in	AC	16 ms	4 MB
clang++-18	out13.in	AC	20 ms	4 MB
clang++-18	out14.in	AC	16 ms	4 MB
clang++-18	out15.in	AC	17 ms	4 MB
clang++-18	out2.in	AC	4 ms	4 MB
clang++-18	out3.in	AC	4 ms	4 MB
clang++-18	out4.in	AC	4 ms	4 MB
clang++-18	out5.in	AC	4 ms	4 MB
clang++-18	out6.in	AC	21 ms	4 MB
clang++-18	out7.in	AC	19 ms	4 MB
clang++-18	out8.in	AC	19 ms	4 MB
clang++-18	out9.in	AC	18 ms	4 MB

Back to top page