zyz /bx /bx /bx
最小公倍树
https://www.luogu.com.cn/problem/P8207
- 会想到从数论角度优化。需要想到最小化 lcm \(\to\) 最大化 gcd。
枚举 gcd \(u\)，那么 \(u\) 的倍数在 \([L,R]\) 中呈现为 \(k\cdot u,(k+1)\cdot u,(k+2)\cdot u,\cdots\)。虽然这些数两两之间的 gcd 并不一定为 \(u\)，但我们在枚举时『钦定』\(u\) 就是 gcd，故贪心地将所有 \(k+i\) 和 \(k\) 连边。
这种钦定的思想是很重要但我不太容易想到的。许多关于『最优化』的转化都会用到这种钦定的想法。
优化建图后跑 Kruskal 即可。
古老代码
#include <bits/stdc++.h>
#define int long long
namespace fastIO {
const int LEN = (1 << 20);
#ifdef ONLINE_JUDGE
inline int nec(void) {
static char buf[LEN], *p = buf, *e = buf;
if (p == e) {
e = buf + fread(buf, 1, LEN, stdin);
if (e == buf) return EOF;
p = buf;
}
return *p++;
}
#else
#define nec getchar
#endif
inline bool read(int &x) {
x = 0;
bool f = 0;
char ch = nec();
while (ch < '0' || ch > '9') {
if (ch == EOF) return 0;
if (ch == '-') f = 1;
ch = nec();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = nec();
}
if (f) x = -x;
return 1;
}
void print(int x) {
if (x < 0)
putchar('-'), x = -x;
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
return;
}
void print(int x, char ch) {
print(x), putchar(ch);
return;
}
} // namespace fastIO
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e6 + 5;
struct _ {
int x, y, w;
_() {}
_(int x1, int y1, int w1) {
x = x1, y = y1, w = w1;
}
bool operator< (const _ &q) const {
return w < q.w;
}
};
int f[maxn];
std::vector<_> e;
int n, res, l, r;
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void merge(int x, int y) { f[find(x)] = find(y); }
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
int main() {
read(l), read(r);
for (int i = 1; i <= r; ++i) {
f[i] = i;
int x = ((l + i - 1) / i) * i;
for(int y = x + i; y <= r; y += i)
e.emplace_back(x, y, lcm(x, y));
}
std::sort(e.begin(), e.end());
for (auto i : e) {
if (find(i.x) != find(i.y))
merge(i.x, i.y), res += i.w;
}
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef int
int main() {
XSC062::main();
return 0;
}色
http://222.180.160.110:61235/problem/46791
- 容易发现相当于在问最短的边，满足两端颜色不同
进一步地，『最短边』问题应该思考边是否一定在 mst 上，就可以借助树的结构。考虑证明：
若 Kruskal 时，边两端的连通块内部都是同色的，且二者不同色，则这条边是最短的异色边。
问题转化为问树上最短异色边。乍一看好像和图没什么区别，困境还是『一次修改影响边数太多』，或『无法简单判定边的类型转化』。
树上问题经验不足。可以分为儿子和父亲维护，儿子整体维护每个颜色的个数，对父亲暴力修改即可。
- 另一种做法是，忽略 mst 性质，对图上的边序列排序后分块。
- 询问时枚举所有块，如果该块中存在异色边，则暴力枚举块中边然后 break。
修改则是祖传哈希，给每条边、每个颜色赋一个随机系数并强行有向化，起点为加终点为减
记录每个块中的系数和，最后总和为 0 则块不可选。
古老代码
#include <bits/stdc++.h>
using ull = unsigned long long;
const int maxk = 555;
const int maxn = 2e5 + 5;
const int maxm = 3e5 + 5;
struct _ { int u, v, w; };
_ g[maxm];
int l[maxk], r[maxk], a[maxn];
ull hash[maxm], w[maxk], to[maxn], val[maxk][maxn];
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#else
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
int n, m, q;
std::cin >> n >> m >> q >> q;
std::mt19937_64 rnd(0xabcdef);
for (int i = 1; i <= m; ++i) {
std::cin >> g[i].u >> g[i].v >> g[i].w;
hash[i] = rnd();
}
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
for (; !to[a[i]]; to[a[i]] = rnd());
}
std::sort(g + 1, g + m + 1, [](_ x, _ y) { return x.w < y.w; });
int siz = sqrt(m), k = (m + siz - 1) / siz;
for (int i = 1; i <= k; ++i) {
l[i] = r[i - 1] + 1, r[i] = std::min(l[i] + siz - 1, m);
for (int j = l[i]; j <= r[i]; ++j) {
val[i][g[j].u] += hash[j];
val[i][g[j].v] -= hash[j];
w[i] += hash[j] * (to[a[g[j].u]] - to[a[g[j].v]]);
}
}
for (int x, y; q--; ) {
std::cin >> x >> y;
for (; !to[y]; to[y] = rnd());
for (int i = 1; i <= k; ++i)
w[i] += val[i][x] * (to[y] - to[a[x]]);
a[x] = y;
for (int i = 1; i <= k; ++i) {
if (w[i]) {
for (int j = l[i]; j <= r[i]; ++j)
if (a[g[j].u] != a[g[j].v]) {
std::cout << g[j].w << '\n';
break;
}
break;
}
}
}
return 0;
}DFS Trees
https://www.luogu.com.cn/problem/CF1707C
一个结论：若图中边权两两不同，则图的最小生成树唯一。
借鉴次小生成树的思路证明…
对于两个 mst \(T_1,T_2\)，假设二者边集不同但权值相同，对于其对称差 \(S\)，设 \(e\) 是其中最小的边，且 \(e\in T_1,e\notin T_2\)。
将 \(e\) 加入 \(T_2\)，则形成的环上存在 \(e'\) 使得 \(e'\in T_2,e'\notin T_1\)，那么 \(e'\in S\)。删掉 \(e'\) 并加入 \(e\)，得到 \(T_2'\)。
由于 \(e\) 是 \(S\) 中最小边，那么 \(e<e'\)。也即 \(T_2'<T_1\)，与前提矛盾。
知道了这一点，就很好从 DFS 树的方向下手了。考虑如何什么时候 DFS 树就是 mst。
对于一条非 mst 树边 \((u,v,w)\)：
- 由 DFS 树的性质，若其为横叉边，必被经过。
- 由 mst 的性质，\(w\) 一定比 \(u,v\) 简单路径上的所有边边权更大，也即，当可以走这条路径时，一定不走 \(w\)。
结合起来，\(w\) 不被经过，当且仅当 \(u,v\) 间存在祖孙关系。对应子树即为合法根。实现时还是需要倍增来找到差分范围，较为难受。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::pair<int, int> > e(m + 1);
for (int i = 1; i <= m; ++i)
std::cin >> e[i].first >> e[i].second;
std::vector<int> f(n + 1);
std::iota(f.begin() + 1, f.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
auto merge = [&](int x, int y) {
f[find(x)] = find(y);
return;
};
std::vector<std::pair<int, int> > u;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1; i <= m; ++i) {
auto &[x, y] = e[i];
if (find(x) != find(y)) {
g[x].push_back(y), g[y].push_back(x);
merge(x, y);
}
else
u.push_back(e[i]);
}
std::vector<int> dep(n + 1);
std::vector<std::array<int, 19> > fa(n + 1);
std::function<void(int)> DFS = [&](int x) {
for (auto i : g[x])
if (i != fa[x][0]) {
dep[i] = dep[x] + 1;
fa[i][0] = x;
for (int j = 1; j < 19; ++j)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
DFS(i);
}
return;
};
dep[1] = 1, DFS(1);
auto ask = [&](int x, int y) {
if (dep[x] < dep[y])
std::swap(x, y);
for (int i = 18; ~i; --i)
if (dep[fa[x][i]] >= dep[y])
x = fa[x][i];
if (x == y)
return x;
for (int i = 18; ~i; --i)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
};
std::vector<int> diff(n + 1);
for (auto [x, y] : u) {
++diff[x], ++diff[y];
if (dep[x] < dep[y])
std::swap(x, y);
if (ask(x, y) == y) {
for (int i = 18; ~i; --i)
if (dep[fa[x][i]] > dep[y])
x = fa[x][i];
--diff[x];
}
}
std::vector<int> res(n + 1);
std::function<void(int, int)> DFS1 = [&](int x, int s) {
s += diff[x];
res[x] = (s == (int)u.size());
for (auto i : g[x])
if (i != fa[x][0])
DFS1(i, s);
return;
};
DFS1(1, 0);
for (int i = 1; i <= n; ++i)
std::cout << res[i];
std::cout << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}Minimum spanning tree for each edge
https://www.luogu.com.cn/problem/CF609E
挺没意思的题…… 略了。
考虑这个题的孪生版本：
Minimum Spanning Tree
https://www.luogu.com.cn/problem/AT_icpc2013spring_e
用非树边更新环上每条树边的最小取代边即可。类似树上差分。代码略。
Power Tree
https://www.luogu.com.cn/problem/CF1120D
- 容易想到把原问题转化为叶子序列上的差分。那么对于任意一个初始差分序列，我们都需要把它通过这样的差分操作变为 \(1\sim n\) 全 0，第 \(n+1\) 位为 \(-s\)。
- 联想到差分和连有向边的转化，那么要求连一个 \(n+1\) 为唯一汇点的树出来。显然就是原图的 mst。
考虑怎么求出可能被 mst 包含的边。对于每一条非树边，若环上存在边权相同的边，那么这条非树边也能成为树边。
考虑一个孪生问题：怎么求出一定被 mst 包含的边？
https://www.luogu.com.cn/problem/CF160D
树上差分 + 线段树合并即可，注意单次线段树合并只有线性，直接做 DSU on tree 的复杂度是单 log 的。
关于具体实现，可以参考 最小生成树的唯一性 - OI Wiki。
#include <bits/stdc++.h>
#define int long long
namespace fastIO {
const int LEN = (1 << 20);
#ifdef ONLINE_JUDGE
inline int nec(void) {
static char buf[LEN], *p = buf, *e = buf;
if (p == e) {
e = buf + fread(buf, 1, LEN, stdin);
if (e == buf) return EOF;
p = buf;
}
return *p++;
}
#else
#define nec getchar
#endif
inline bool read(int &x) {
x = 0;
bool f = 0;
char ch = nec();
while (ch < '0' || ch > '9') {
if (ch == EOF) return 0;
if (ch == '-') f = 1;
ch = nec();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = nec();
}
if (f) x = -x;
return 1;
}
void print(int x) {
if (x < 0)
putchar('-'), x = -x;
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
return;
}
void print(int x, char ch) {
print(x), putchar(ch);
return;
}
} // namespace fastIO
namespace XSC062 {
using namespace fastIO;
const int maxn = 2e5 + 5;
struct _ {
int x, y, i;
_() {}
_(int x1, int y1, int i1) {
x = x1, y = y1, i = i1;
}
bool operator< (const _ &q) const;
};
_ t[maxn];
int a[maxn], f[maxn];
std::vector<int> res;
int n, now, x, y, sum;
int beg[maxn], to[maxn];
std::vector<int> g[maxn];
bool _::operator< (const _ &q) const {
return a[i] < a[q.i];
}
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void merge(int x, int y) {
f[find(x)] = find(y);
return;
}
void DFS(int x, int fa) {
if (~fa && (int)g[x].size() == 1)
beg[x] = to[x] = ++now;
for (auto i : g[x]) {
if (i == fa) continue;
DFS(i, x);
if (!beg[x]) beg[x] = beg[i];
to[x] = to[i];
}
t[x] = _(beg[x], to[x] + 1, x);
return;
}
void add(int x, int y) {
g[x].push_back(y);
return;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= n + 1; ++i) f[i] = i;
for (int i = 1; i < n; ++i) {
read(x), read(y);
add(x, y), add(y, x);
}
DFS(1, -1);
std::sort(t + 1, t + n + 1);
for (int l = 1, r = 0; l <= n; l = r + 1) {
while (r < n && a[t[r + 1].i] == a[t[l].i]) ++r;
for (int i = l; i <= r; ++i) {
if (find(t[i].x) != find(t[i].y))
res.push_back(t[i].i);
}
for (int i = l; i <= r; ++i) {
if (find(t[i].x) != find(t[i].y))
sum += a[t[i].i], merge(t[i].x, t[i].y);
}
}
std::sort(res.begin(), res.end());
print(sum, ' '), print(res.size(), '\n');
for (auto i : res) print(i, ' ');
putchar('\n');
return 0;
}
} // namespace XSC062
#undef int
int main() {
XSC062::main();
return 0;
}Another Minimum Spanning Tree
http://222.180.160.110:61235/problem/29212
goto 曼哈顿最小距离生成树。
A - Design Tutorial: Inverse the Problem
https://www.luogu.com.cn/problem/CF472D
- 发现给出的完全图的最小生成树就是原树。check 一下是否合法即可。
- 图较稠密，需要用 Prim。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
std::vector<std::vector<int> > g0(n + 1, std::vector<int> (n + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
std::cin >> g0[i][j];
for (int i = 1; i <= n; ++i) {
if (g0[i][i] != 0) {
std::cout << "NO\n";
return 0;
}
for (int j = 1; j < i; ++j)
if (g0[i][j] != g0[j][i] || !g0[i][j]) {
std::cout << "NO\n";
return 0;
}
}
std::vector<int> pos(n + 1), tag(n + 1);
tag[1] = 1;
for (int _ = 1, s = 1; _ < n; ++_) {
for (int i = 1; i <= n; ++i)
if (!tag[i] && (!pos[i] || g0[s][i] < g0[pos[i]][i]))
pos[i] = s;
s = 0;
int t = 0;
for (int i = 1; i <= n; ++i)
if (!tag[i] && pos[i] && (!s || g0[pos[i]][i] < g0[pos[s]][s]))
s = i, t = pos[i];
tag[s] = 1;
g[s].emplace_back(t, g0[s][t]), g[t].emplace_back(s, g0[s][t]);
}
std::vector<int> tab(n + 1), dis(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
static int now = 0;
tab[++now] = x;
int L = now, R = now;
for (auto [i, w] : g[x])
if (i != fa) {
dis[i] = dis[x] + w;
DFS(i, x);
for (int p = L; p <= R; ++p)
for (int q = R + 1; q <= now; ++q) {
if (g0[tab[p]][tab[q]] != dis[tab[p]] + dis[tab[q]] - 2 * dis[x]) {
std::cout << "NO\n";
exit(0); // extremely ugly
}
}
R = now;
}
return;
};
DFS(1, -1);
std::cout << "YES\n";
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B - Phoenix and Earthquake
https://www.luogu.com.cn/problem/CF1515F
会想到，有解的充要条件是的点权之和 \(\ge (n-1)\cdot x\)。证明方法很广泛，但规约的思想对破题是决定性的。
对于 \(u\ge x\)，将 \(u\) 和任意相邻点合并后缩点，规约为更小规模的问题。
对于 \(u<x\)，一次合并使点权和减少 \(u\)，点权需求减少 \(x\)，故子问题合法则该问题合法。
条件是充要的，则可以任意合并，但这样不太好做，考虑借助规约的结构，若 \(u\ge x\) 则直接合并，否则等到其他部分合并完后再合并这一条边。这是一个栈的结构。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m, k;
std::cin >> n >> m >> k;
std::vector<long long> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
if (std::accumulate(a.begin() + 1, a.end(), 0ll) < (long long)k * (n - 1)) {
std::cout << "NO\n";
return 0;
}
std::cout << "YES\n";
std::vector<int> f(n + 1);
std::iota(f.begin() + 1, f.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
auto merge = [&](int x, int y) {
f[find(x)] = find(y);
return;
};
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
for (int i = 1, x, y; m--; ++i) {
std::cin >> x >> y;
if (find(x) != find(y)) {
g[x].emplace_back(y, i);
g[y].emplace_back(x, i);
merge(x, y);
}
}
std::vector<int> t;
std::function<void(int, int)> DFS = [&](int x, int fa) {
for (auto [i, id] : g[x])
if (i != fa) {
DFS(i, x);
if (a[i] >= k) {
a[x] += a[i] - k;
std::cout << id << '\n';
}
else
t.push_back(id);
}
return;
};
DFS(1, -1);
for (; !t.empty(); t.pop_back())
std::cout << t.back() << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}最小度限制生成树 (Easy Version)
https://www.luogu.com.cn/problem/P5633
要求：两只 log。
wqs 二分即可。
最小度限制生成树 (Hard Version)
要求：一只 log。
注意到涉及的边是固定的，且偏移量相同，故对于『与 \(s\) 有关的边』和『与 \(s\) 无关的边』先分别排序作为预处理，二分内部仅需归并即可。
最小度限制生成树 (Extreme Version)
要求：
- 一只 log；
- 对于 \(k=1,2,\cdots,n\)，分别输出答案。