本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-02 21:46:52
似乎没有题解提到枚举二进制位这个 trick，就发一篇题解。
由于边的信息可以通过点的信息表示出来，并且边很多，无法直接存储，考虑使用 Boruvka 算法。
考虑每一轮加边该如何处理。
考虑将加边前的图中每个节点所在的连通块编号视为这个点的类别。
考虑正常算法流程，对于每个连通块，都需要找到其他连通块中最优的点，使得本连通块与之建的边权是最小的。
显然，本轮需要加入的边所连接的两个点的类别肯定是不同的。
考虑朴素做法，正着扫一遍再反着扫一遍，扫描的过程中必然需要记录每个类别的最优点是哪个。
这样的话，有 $O(\log V)$ 级别的加边轮数，每次扫描复杂度 $O(n^2)$，炸了。
考虑简化上述过程。上述过程的本质在于任意两个不同类别的点都需要 chk 一次。
考虑这样一个 trick：枚举每个二进制位，仅对类别编号在这一位不同的点对进行处理。
这样的话，每次处理过程只需要 $O(n)$ 扫一遍（不是 $O(n^2)$ 是因为这里从 $n$ 种类别变成了两种类别，即这一位是 $0$ 还是 $1$）。
复杂度变为 $O(n \log n \log V )$ 。
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
template <class T>
void ckmx(T &a, T b) { a = max(a, b); }
template <class T>
void ckmn(T &a, T b) { a = min(a, b); }
template <class T>
T gcd(T a, T b) { return !b ? a : gcd(b, a % b); }
template <class T>
T lcm(T a, T b) { return a \/ gcd(a, b) * b; }
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template <class T>
void wrint(T x)
{
if (x < 0)
{
x = -x;
pc('-');
}
if (x >= 10)
{
wrint(x \/ 10);
}
pc(x % 10 ^ 48);
}
template <class T>
void wrintln(T x)
{
wrint(x);
pln
}
template <class T>
void read(T &x)
{
x = 0;
int f = 1;
char ch = gc;
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = gc;
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = gc;
}
x *= f;
}
const int maxn = 2e5 + 5;
int n;
ll d, a[maxn];
struct MS
{
int fa[maxn];
int get(int x) { return (fa[x] == x ? x : fa[x] = get(fa[x])); }
void ms(int a, int b)
{
if (get(a) != get(b))
{
fa[get(a)] = get(b);
}
}
void init() { FOR(i, 1, n)
fa[i] = i; }
} ms;
ll mn[maxn];
int mnid[maxn];
bool at(int s, int i) { return (s & (1 << i)); }
void solve(int id_of_test)
{
read(n);
read(d);
FOR(i, 1, n) { read(a[i]); }
ms.init();
ll ans = 0;
while (1)
{
memset(mn, 0x7f, sizeof mn);
memset(mnid, 0, sizeof mnid);
bool flg = 0;
FOR(bit, 0, 17)
{
{
ll _mn = mn[0];
int _mnid = 0;
FOR(i, 1, n)
{
_mn += d;
if (at(ms.get(i), bit))
{
if (_mn + a[i] < mn[ms.get(i)])
{
mnid[ms.get(i)] = _mnid;
mn[ms.get(i)] = _mn + a[i];
}
}
if (!at(ms.get(i), bit))
{
if (_mn > a[i])
{
_mn = a[i];
_mnid = i;
}
}
}
_mn = mn[0];
_mnid = 0;
REP(i, n, 1)
{
_mn += d;
if (at(ms.get(i), bit))
{
if (_mn + a[i] < mn[ms.get(i)])
{
mn[ms.get(i)] = _mn + a[i];
mnid[ms.get(i)] = _mnid;
}
}
if (!at(ms.get(i), bit))
{
if (_mn > a[i])
{
_mn = a[i];
_mnid = i;
}
}
}
}
{
ll _mn = mn[0];
int _mnid = 0;
FOR(i, 1, n)
{
_mn += d;
if (!at(ms.get(i), bit))
{
if (_mn + a[i] < mn[ms.get(i)])
{
mnid[ms.get(i)] = _mnid;
mn[ms.get(i)] = _mn + a[i];
}
}
if (at(ms.get(i), bit))
{
if (_mn > a[i])
{
_mn = a[i];
_mnid = i;
}
}
}
_mn = mn[0];
_mnid = 0;
REP(i, n, 1)
{
_mn += d;
if (!at(ms.get(i), bit))
{
if (_mn + a[i] < mn[ms.get(i)])
{
mn[ms.get(i)] = _mn + a[i];
mnid[ms.get(i)] = _mnid;
}
}
if (at(ms.get(i), bit))
{
if (_mn > a[i])
{
_mn = a[i];
_mnid = i;
}
}
}
}
}
FOR(i, 1, n)
{
if (mnid[i])
{
if (ms.get(i) == ms.get(mnid[i]))
continue;
ms.ms(i, mnid[i]);
flg = 1;
ans += mn[i];
}
}
if (!flg)
{
break;
}
}
printf("%lld\n", ans);
}
int main()
{
int T;
T = 1;
FOR(_, 1, T) { solve(_); }
return 0;
}
鲁ICP备2025150228号