还是推荐用 LOJ 评测,可以评测全部的数据
Description
给一个简单一些的题面
有一张 $n$ 个点 $m$ 条边的带权无向图, 均从 $0$ 开始编号.现在有 $Q$ 组询问,每次两个人从 $u,v$ 出发,要求这两个人不能同时在一个点上,也不能同时经过一条边.允许多次走一个点或者一条边.
现在要求最小化路径上的最大边权.
Sol
APIO2021来之前决定做一些 APIO 的真题来练练手
APIO 的题都是用实现函数类似于交互库的形式, 还是要提前适应
首先看到最小化最大这种东西,可以先试着往二分上靠.那么就二分这个答案最大权,每次两个点丢进去暴跳的途中判断就完事儿了.可能要注意下细节.应该可以拿到 Subtask3 的部分分
现在二分判定的瓶颈不在二分出答案上面,而是在判定答案时我是爆判的.考虑来优化这个过程.最简单的情形就是在一条链上面,这个两个人如果同时往中间跳时相遇,就跑不掉了.这样链的答案是 $-1$ . 菊花图的情况对应 Subtask2, 那么只需要判断一下起点和终点经不经过菊花根就可以了.
现在要解决的问题就是什么时候一定会有答案. 已知链无解,无解是因为必要同时经过同一边.但凡有一条别的出边能出去,就有可能有解. 假如现在有这么一条边能让它出去了,要再让他回来到达终点就必须有一条边引回.这样就是一个三元环.(这个过程可以多画画图)
解决了这个问题,二分的方法复杂度是 $O(Qn \log n)$ .可以通过 Subtask4
解决问题的关键又变成了二分不够优秀.考虑 Kruskal 重构树.可以用来解决这个问题. 在 Kruskal 重构树上, $u, v$ 路径上的最小被阀值限制的边权就是它们 lca 的点权.
还有一个问题就是做 Kruskal 的时候还要注意连通块是不是链的问题.可以这么解决,同时维护一个连通块的起点和终点,以及连通块的一个根.合并的时候注意,分情况讨论.
- 现在两个连通块要合并,不是链的话合并以后也不是
还不能合并:
- 有一个不是新的就不是
- 原来两个都是链,那么就看是不是两条链的端点连边,如果是的话就会连成一条链.
Code
Luogu 的不要加 swap.h 这一句
#include <bits/stdc++.h>
#include "swap.h"
const int SIZE = 3e5 + 5;
int num, idx, tim, n;
int head[SIZE], vis[SIZE], w[SIZE], st[SIZE], ed[SIZE], fa[SIZE], dfn[SIZE], root[SIZE], f[SIZE][21];
std::vector < int > chain[SIZE];
struct node {
int to, nxt;
} edge[SIZE << 1];
struct E {
int from, to, v;
bool operator< (const E a) const {
return v < a.v;
}
} e[SIZE];
void addEdge(int u, int v) {
edge[++ num] = (node) {v, head[u]}, head[u] = num;
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void dfs(int u, int anc) {
dfn[u] = ++ idx;
for (int i = head[u], v; i; i = edge[i].nxt) {
v = edge[i].to;
if (v == anc) continue;
f[v][0] = u, root[v] = !u ? 0 : root[u];
for (int j = 1; j <= 20; ++ j) f[v][j] = f[f[v][j - 1]][j - 1];
// printf("from:%d to:%d\n", u, v);
dfs(v, u);
}
}
void init(int N, int M, std::vector < int > U, std::vector < int > V, std::vector < int > W) {
int tot = 0; tim = N, n = N;
for (int i = 1; i <= M; ++ i) e[i].from = U[i - 1] + 1, e[i].to = V[i - 1] + 1, e[i].v = W[i - 1];
std::sort(e + 1, e + M + 1);
for (int i = 1; i <= N; ++ i) fa[i] = i, st[i] = ed[i] = root[i] = i, chain[i].push_back(i);
for (int i = 1; i <= M; ++ i) {
int x = e[i].from, y = e[i].to;
int fx = find(e[i].from), fy = find(e[i].to); tim = i + N;
if (chain[fx].size() < chain[fy].size()) { std::swap(x, y); std::swap(fx, fy); }
if (fx == fy) {
if (!vis[fx]) {
vis[fx] = 1;
for (auto it: chain[fx]) addEdge(tim, it);
root[fx] = tim;
}
}
else {
if (vis[fx] || vis[fy]) {
if (vis[fx]) addEdge(tim, root[fx]);
else for (auto it: chain[fx]) addEdge(tim, it);
if (vis[fy]) addEdge(tim, root[fy]);
else for (auto it: chain[fy]) addEdge(tim, it);
vis[fx] = 1, root[fx] = tim, fa[fy] = fx;
}
else {
if ((x == st[fx] || x == ed[fx]) && (y == st[fy] || y == ed[fy])) {
st[fx] = x ^ st[fx] ^ ed[fx], ed[fx] = y ^ st[fy] ^ ed[fy];
for (auto it: chain[fy]) chain[fx].emplace_back(it);
fa[fy] = fx;
}
else {
vis[fx] = 1;
for (auto it: chain[fx]) addEdge(tim, it);
for (auto it: chain[fy]) addEdge(tim, it);
fa[fy] = fx, root[fx] = tim;
}
}
}
}
for (int i = N + M; i; -- i) {
if (!dfn[i]) dfs(i, 0);
}
// for (int i = 1; i <= N + M; ++ i) {
// printf("from:%d ", i);
// for (int j = 1; j <= 5; ++ j) printf("%d ", f[i][j]);
// puts("");
// }
}
int lca(int u, int v) {
if (u == v) return u;
if (root[u] != root[v]) return -1;
if (dfn[u] > dfn[v]) std::swap(u, v);
for (int i = 20; ~i; -- i) {
if (dfn[f[v][i]] > dfn[u]) v = f[v][i];
}
return f[v][0];
}
int getMinimumFuelCapacity(int X, int Y) {
++ X, ++ Y;
int anc = lca(X, Y);
if (anc == -1) return -1;
return e[anc - n].v;
}
