proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/minimum_steiner_tree/no_restore.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/1040

#include <iostream>
#include <vector>
#include "atcoder/dsu.hpp"
#include "tools/minimum_steiner_tree.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  while (true) {
    int H, W;
    std::cin >> H >> W;
    if (H == 0 && W == 0) break;

    std::vector grid(H, std::vector<int>(W));
    for (auto&& row : grid) for (auto&& cell : row) std::cin >> cell;

    std::vector<int> terminals;
    for (int r = 0; r < H; ++r) {
      for (int c = 0; c < W; ++c) {
        if (grid[r][c] == 1) terminals.push_back(r * W + c);
      }
    }

    tools::minimum_steiner_tree<int> graph(H * W);
    for (int r = 0; r < H; ++r) {
      for (int c = 0; c < W; ++c) {
        if (r > 0) graph.add_edge(r * W + c, (r - 1) * W + c, 1);
        if (c > 0) graph.add_edge(r * W + c, r * W + (c - 1), 1);
      }
    }

    std::cout << H * W - graph.query(terminals) - 1 << '\n';
  }

  return 0;
}

#line 1 "tests/minimum_steiner_tree/no_restore.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/1040

#include <iostream>
#include <vector>
#line 1 "lib/ac-library/atcoder/dsu.hpp"



#include <algorithm>
#include <cassert>
#line 7 "lib/ac-library/atcoder/dsu.hpp"

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder


#line 1 "tools/minimum_steiner_tree.hpp"



#line 6 "tools/minimum_steiner_tree.hpp"
#include <limits>
#include <queue>
#include <ranges>
#include <stack>
#include <tuple>
#include <type_traits>
#include <utility>
#line 1 "tools/chmin.hpp"



#line 6 "tools/chmin.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/greater_by_second.hpp"



#line 5 "tools/greater_by_second.hpp"

namespace tools {

  class greater_by_second {
  public:
    template <class T1, class T2>
    bool operator()(const ::std::pair<T1, T2>& x, const ::std::pair<T1, T2>& y) const {
      return x.second > y.second;
    }
  };
}


#line 16 "tools/minimum_steiner_tree.hpp"

namespace tools {
  template <typename Cost>
  class minimum_steiner_tree {
  public:
    struct edge {
      int from;
      int to;
      Cost cost;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<int>> m_graph;

  public:
    struct query_result {
      Cost cost;
      ::std::vector<int> vertices;
      ::std::vector<int> edge_ids;
    };

    minimum_steiner_tree() = default;
    explicit minimum_steiner_tree(const int n) : m_graph(n) {
      assert(n >= 0);
    }

    int size() const {
      return this->m_graph.size();
    }
    int add_edge(int u, int v, const Cost w) {
      assert(0 <= u && u < this->size());
      assert(0 <= v && v < this->size());
      assert(w >= 0);

      ::std::tie(u, v) = ::std::minmax({u, v});
      this->m_edges.push_back({u, v, w});
      this->m_graph[u].push_back(this->m_edges.size() - 1);
      this->m_graph[v].push_back(this->m_edges.size() - 1);
      return this->m_edges.size() - 1;
    }
    const edge& get_edge(const int i) const {
      assert(0 <= i && ::std::cmp_less(i, this->m_edges.size()));
      return this->m_edges[i];
    }
    const ::std::vector<edge>& edges() const {
      return this->m_edges;
    }

  public:
    template <bool Restore, ::std::ranges::range R>
    ::std::conditional_t<Restore, query_result, Cost> query(R&& S) const {
      if constexpr (::std::ranges::forward_range<R>) {
        const auto k = ::std::ranges::distance(S);
        assert(0 <= k && k <= this->size());
        assert(::std::ranges::all_of(S, [this](const int v) { return 0 <= v && v < this->size(); }));

        if (k == 0) {
          if constexpr (Restore) {
            return query_result{};
          } else {
            return 0;
          }
        }

        ::std::vector dp(1 << k, ::std::vector(this->size(), ::std::numeric_limits<Cost>::max()));
        ::std::vector prev(Restore ? 1 << k : 0, ::std::vector(this->size(), -1));
        for (int t = 0; const auto v : S) {
          dp[1 << t][v] = 0;
          ++t;
        }
        for (int T = 1; T < 1 << k; ++T) {
          for (int v = 0; v < this->size(); ++v) {
            for (int U = (T - 1) & T; U > 0; U = (U - 1) & T) {
              if (dp[U][v] < ::std::numeric_limits<Cost>::max() && dp[T ^ U][v] < ::std::numeric_limits<Cost>::max() && ::tools::chmin(dp[T][v], dp[U][v] + dp[T ^ U][v])) {
                if constexpr (Restore) {
                  prev[T][v] = U;
                }
              }
            }
          }
          ::std::priority_queue<::std::pair<int, Cost>, ::std::vector<::std::pair<int, Cost>>, ::tools::greater_by_second> pq;
          for (int v = 0; v < this->size(); ++v) {
            if (dp[T][v] < ::std::numeric_limits<Cost>::max()) {
              pq.emplace(v, dp[T][v]);
            }
          }
          while (!pq.empty()) {
            const auto [here, d] = pq.top();
            pq.pop();
            if (dp[T][here] < d) continue;
            for (const auto edge_id : this->m_graph[here]) {
              const auto& edge = this->m_edges[edge_id];
              const auto next = edge.from ^ edge.to ^ here;
              if (::tools::chmin(dp[T][next], dp[T][here] + edge.cost)) {
                pq.emplace(next, dp[T][next]);
                if constexpr (Restore) {
                  prev[T][next] = (1 << k) + edge_id;
                }
              }
            }
          }
        }

        if constexpr (Restore) {
          query_result qr;
          qr.cost = dp.back()[*::std::ranges::begin(S)];
          if (qr.cost == ::std::numeric_limits<Cost>::max()) return qr;

          ::std::stack<::std::pair<int, int>> stack;
          stack.emplace((1 << k) - 1, *::std::ranges::begin(S));
          qr.vertices.push_back(*::std::ranges::begin(S));
          while (!stack.empty()) {
            const auto [T, v] = stack.top();
            stack.pop();
            if (prev[T][v] == -1) continue;
            if (prev[T][v] < 1 << k) {
              stack.emplace(prev[T][v], v);
              stack.emplace(T ^ prev[T][v], v);
            } else {
              const auto edge_id = prev[T][v] - (1 << k);
              const auto& edge = this->m_edges[edge_id];
              qr.vertices.push_back(edge.from ^ edge.to ^ v);
              qr.edge_ids.push_back(edge_id);
              stack.emplace(T, edge.from ^ edge.to ^ v);
            }
          }
          return qr;
        } else {
          return dp.back()[*::std::ranges::begin(S)];
        }
      } else {
        return this->query<Restore>(::std::vector<::std::decay_t<::std::ranges::range_value_t<R>>>(::std::ranges::begin(S), ::std::ranges::end(S)));
      }
    }
    template <::std::ranges::range R>
    auto query(R&& S) const {
      return this->query<false>(::std::forward<R>(S));
    }
  };
}


#line 7 "tests/minimum_steiner_tree/no_restore.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  while (true) {
    int H, W;
    std::cin >> H >> W;
    if (H == 0 && W == 0) break;

    std::vector grid(H, std::vector<int>(W));
    for (auto&& row : grid) for (auto&& cell : row) std::cin >> cell;

    std::vector<int> terminals;
    for (int r = 0; r < H; ++r) {
      for (int c = 0; c < W; ++c) {
        if (grid[r][c] == 1) terminals.push_back(r * W + c);
      }
    }

    tools::minimum_steiner_tree<int> graph(H * W);
    for (int r = 0; r < H; ++r) {
      for (int c = 0; c < W; ++c) {
        if (r > 0) graph.add_edge(r * W + c, (r - 1) * W + c, 1);
        if (c > 0) graph.add_edge(r * W + c, r * W + (c - 1), 1);
      }
    }

    std::cout << H * W - graph.query(terminals) - 1 << '\n';
  }

  return 0;
}

Test cases

Env Name Status Elapsed Memory
g++ judge_data :heavy_check_mark: AC 17 ms 4 MB
Back to top page