"combinatorial_opt/test/mincostflow.radixheaparray.yuki1288.test.cpp": "2021-09-08 01:27:01 +0900",

"data_structure/test/radix_heap_array.dijkstra.test.cpp": "2021-09-08 01:27:01 +0900",

#define PROBLEM "https://yukicoder.me/problems/no/1288"

#include "../../data_structure/radix_heap_array.hpp"

#include "../mincostflow_nonegativeloop.hpp"

#include <iostream>

#include <numeric>

#include <string>

#include <vector>

using namespace std;

int main() {

int N;

string S;

cin >> N >> S;

vector<long long> V(N);

for (auto &x : V) cin >> x;

const int s = N * 5, t = s + 1;

MinCostFlow<int, long long> graph(t + 1);

for (int d = 0; d < 5; d++) {

for (int i = 0; i < N - 1; i++) graph.add_edge(d * N + i, d * N + i + 1, N / 4, 0);

}

graph.add_edge(s - 1, 0, N / 4, 0);

for (int i = 0; i < N; i++) {

int b = 0;

if (S[i] == 'u') b = N * 1;

if (S[i] == 'k') b = N * 2;

if (S[i] == 'i') b = N * 3;

int fr = b + i + N, to = b + i;

graph.add_edge(s, fr, 1, 0);

graph.add_edge(fr, to, 1, V[i]);

graph.add_edge(to, t, 1, 0);

}

auto cost = graph.flow<radix_heap_array<unsigned long long>>(s, t, N).second;

cout << accumulate(V.begin(), V.end(), 0LL) - cost << '\n';

}

#pragma once

#include <array>

#include <limits>

#include <type_traits>

#include <utility>

#include <vector>

template <class Uint> class radix_heap_array {

int sz;

Uint last;

std::array<std::vector<std::pair<Uint, int>>, std::numeric_limits<Uint>::digits + 1> v;

struct smallpii {

unsigned b : 7;

int j : 25;

};

std::vector<smallpii> i2bj;

template <class U, typename std::enable_if<sizeof(U) == 4>::type* = nullptr>

static inline unsigned bucket(U x) noexcept {

return x ? 32 - __builtin_clz(x) : 0;

}

template <class U, typename std::enable_if<sizeof(U) == 8>::type* = nullptr>

static inline unsigned bucket(U x) noexcept {

return x ? 64 - __builtin_clzll(x) : 0;

}

void pull() {

if (!v[0].empty()) return;

int b = 1;

while (v[b].empty()) ++b;

last = v[b].back().first;

for (int j = 0; j < int(v[b].size()); j++) last = std::min(last, v[b][j].first);

for (int j = 0; j < int(v[b].size()); j++) {

int i = v[b][j].second;

auto bnxt = bucket(v[b][j].first ^ last);

i2bj[i] = {bnxt, int(v[bnxt].size())}, v[bnxt].emplace_back(std::move(v[b][j]));

}

v[b].clear();

}

radix_heap_array() : sz(0), last(0) {}

bool empty() const noexcept { return sz == 0; }

int argmin_pop() {

pull(), --sz;

int i = v[0].back().second;

i2bj[i].j = -1;

v[0].pop_back();

return i;

}

void chmin(Uint vnew, int i) {

if (i >= int(i2bj.size())) i2bj.resize(i + 1, {0, -1});

if (i2bj[i].j < 0) {

auto b = bucket(vnew ^ last);

++sz, i2bj[i] = {b, int(v[b].size())}, v[b].emplace_back(vnew, i);

} else if (v[i2bj[i].b][i2bj[i].j].first > vnew) {

auto bold = i2bj[i].b, bnew = bucket(vnew ^ last);

if (bnew < bold) {

int ilast = v[bold].back().second, j = i2bj[i].j;

std::swap(v[bold][j], v[bold].back());

i2bj[ilast].j = j, i2bj[i] = {bnew, int(v[bnew].size())};

v[bnew].emplace_back(vnew, i), v[bold].pop_back();

} else {

v[bold][i2bj[i].j].first = vnew;

}

}

}

void pop() { argmin_pop(); }

std::pair<Uint, int> top() { return pull(), v[0].back(); }

[[deprecated("NOT usual emplace() opeation!")]] void emplace(Uint vnew, int i) { chmin(vnew, i); }

void clear() noexcept { sz = 0, last = 0, i2bj.clear(); }

};

title: Array-like radix heap with decrease query（`chmin()` 操作が可能な基数ヒープ）

documentation_of: ./radix_heap_array.hpp

`radix_heap.hpp` におけるラベルを非負整数に限り，更にラベル $i$ に対応したキーに対する decrease 操作（いわゆる `chmin`）を $O(1)$ で行えるもの．

以下のように，Dijkstra 法を効率的に実行可能なクエリが揃っている．以下，$D$ を `UnsignedInt` 型のビット数とする．

- `radix_heap_array<UnsignedInt>()`: Radix heap の初期化．各 $i \ge 0$ について $A_i = \infty$ と初期化．計算量は $O(D)$．

- `bool empty()`: $A\_i < \infty$ である $i$ が存在しないとき，及びそのときに限り `true` を返す．$O(1)$

- `int argmin_pop()`: $A\_i$ が最小値をとる $i$ を一つとって $A\_i = \infty$ と更新し，$i$ を返す．償却 $O(D)$

- `void chmin(UnsignedInt x, int i)`: $A\_i$ を $\min(A\_i, x)$ で更新する．$x$ の値はこれまで `pop()` や `top()` の対象となった最大の値以上でなければならない．$O(1)$

以下は既存のライブラリとの互換性のために実装されている．

- `void pop()`: $A\_i$ が最小の $i$ の一つについて，$A_i = \infty$ と更新する．償却 $O(D)$

- `pair<UnsignedInt, int> top()`: $A\_i$ が最小の $i$ の一つについて，$(A\_i, i)$ の組を返す．償却 $O(D)$

- `void emplace(Uint vnew, int i)` （非推奨）: `chmin()` と同じ効果で，STL における同名の関数とは意味が大きく異なる．既存のライブラリに含まれる `priority_queue` をコンテスト中に素早くこのライブラリに置き換えることを可能にするためにのみ存在している．$O(1)$

Dijkstra 法による最短 $s$ - $t$ パスの計算は次のように書ける：

vector<unsigned long long> dist(N, numeric_limits<unsigned long long>::max());

vector<int> prv(N, -1);

dist[s] = 0;

radix_heap_array<unsigned long long> pq;

pq.chmin(0, s);

while (!pq.empty()) {

int now = pq.argmin_pop();

if (now == t) break;

for (const auto &nx : to[now]) {

int nxt = nx.first;

if (dist[nxt] > dist[now] + nx.second) {

dist[nxt] = dist[now] + nx.second;

prv[nxt] = now;

pq.chmin(dist[nxt], nxt);

}

}

}

#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"

#include "../radix_heap_array.hpp"

#include "../../utilities/reader.hpp"

#include <iostream>

#include <limits>

#include <utility>

#include <vector>

using namespace std;

int main() {

cin.tie(nullptr), ios::sync_with_stdio(false);

int N = rdi(), M = rdi(), s = rdi(), t = rdi();

vector<vector<pair<int, unsigned>>> to(N);

while (M--) {

int a = rdi(), b = rdi(), c = rdi();

to[b].emplace_back(a, c);

}

vector<unsigned long long> dist(N, numeric_limits<unsigned long long>::max());

vector<int> prv(N, -1);

dist[t] = 0;

radix_heap_array<unsigned long long> pq;

pq.chmin(0, t);

while (!pq.empty()) {

int now = pq.argmin_pop();

if (now == s) break;

for (const auto &nx : to[now]) {

int nxt = nx.first;

if (dist[nxt] > dist[now] + nx.second) {

dist[nxt] = dist[now] + nx.second;

prv[nxt] = now;

pq.chmin(dist[nxt], nxt);

}

}

}

if (dist[s] == numeric_limits<unsigned long long>::max()) {

cout << "-1\n";

return 0;

}

std::vector<int> path;

for (int now = s; now != -1; now = prv[now]) path.push_back(now);

cout << dist[s] << ' ' << path.size() - 1 << '\n';

for (int i = 1; i < int(path.size()); i++) cout << path[i - 1] << ' ' << path[i] << '\n';

}