CodeForces 1648E Air Reform
洛谷传送门
CF 传送门
被一道题创了三天
我们先考虑如何求给定两点在原图的最短路。套路地，建出 Kruskal 重构树，最短路就是两点 \(\text{LCA}\) 的权值。
对于在补图的最短路，我们希望如法炮制，建出补图的 Kruskal 重构树。但是由于边数太多无法跑 Kruskal。不妨退一步，建出补图的最小生成树，那么两点的最短路就是这两点在最小生成树上的简单路径的最大边权。
求一个稠密图的最小生成树，可以考虑 Boruvka 算法。其思想基于每个点的最短邻边一定在最小生成树上，流程是每轮对每个连通块找到一条连向另一连通块的最短边，然后合并两端点。因为每轮连通块数量至少减半，所以一共会进行 \(O(\log n)\) 轮。
于是现在我们考虑对每个点 \(u\)，求出它连出去的最小出边，并且边的另一端点不和 \(u\) 在同一连通块。我们不妨倍增找到 \(u\) 在 Kruskal 重构树上的最浅祖先，使得它包含的所有叶子不是都和 \(u\) 在同一连通块。
考虑把 Kruskal 重构树拍平到序列上，那么每个点的子树管辖 dfn 序在 \([l_i, r_i]\) 中的叶子。设 \(f_i\) 为 \(i\) 所在连通块的代表元，\(g_i\) 为 dfn 序为 \(i\) 的点，\(d_i\) 为最大的 \(j\) 使得 \(\forall k \in [j, i], f_{g_k} = f_{g_i}\)，也就是说 \(g_{d_i - 1}\) 是 \(i\) 在 dfn 序上往左第一个与 \(g_i\) 不在同一连通块的点。
考虑倍增到 \(u\) 的一个祖先 \(v\) 后，如何判定 \(v\) 子树管辖的叶子不是都和 \(u\) 在同一连通块，并且如果这个条件满足，还要找到这样的一个叶子。如果 \(g_{r_v}\) 不和 \(u\) 在同一连通块，那么 \(g_{r_v}\) 即为所求。否则，dfn 序在 \([d_{r_v}, r_v]\) 中的叶子都和 \(u\) 在同一连通块，若 \(d_{r_v} > l_v\)，那么 \(g_{d_{r_v} - 1}\) 即为所求，否则 \(v\) 不满足条件。
但是有个问题，因为我们求的是补图的最小生成树，所以找到的边不能是原图上有的边。考虑判定 \(v\) 是否满足条件时，对于所有 \(u\) 在原图上连出去的边 \((u, w)\)，\(l_w\) 把 \([l_v, r_v]\) 分成了 \(O(deg_u)\) 个小区间。因为 \(O(\sum deg_u) = O(m)\)，所以我们可以暴力找到 \(O(deg_u)\) 个小区间，再按照上面的方法判定即可。
时间复杂度 \(O(m (\log^2 n + \log m))\)。
code
// Problem: E. Air Reform
// Contest: Codeforces - Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)
// URL: https://codeforces.com/problemset/problem/1648/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 400100;
const int logn = 21;
int n, m, times, ff[maxn], a[maxn], f[maxn][logn], d[maxn];
int st[maxn], ed[maxn], rnk[maxn], dep[maxn], sz[maxn], ans[maxn];
pii c[maxn];
vector<int> G[maxn], gg[maxn];
vector<pii> T[maxn];
struct edg {
int u, v, d, id;
edg(int a = 0, int b = 0, int c = 0, int e = 0) : u(a), v(b), d(c), id(e) {}
} E[maxn];
int find(int x) {
return ff[x] == x ? x : ff[x] = find(ff[x]);
}
inline bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
ff[x] = y;
return 1;
} else {
return 0;
}
}
void dfs(int u) {
if (u <= n) {
st[u] = ++times;
rnk[times] = u;
} else {
st[u] = times + 1;
}
for (int v : G[u]) {
f[v][0] = u;
dep[v] = dep[u] + 1;
dfs(v);
}
ed[u] = times;
}
int fa[maxn], son[maxn], top[maxn], dfn[maxn], b[maxn];
int dfs2(int u, int f, int d) {
fa[u] = f;
sz[u] = 1;
dep[u] = d;
int mx = -1;
for (pii p : T[u]) {
int v = p.fst, k = p.scd;
if (v == f) {
continue;
}
b[v] = k;
sz[u] += dfs2(v, u, d + 1);
if (sz[v] > mx) {
son[u] = v;
mx = sz[v];
}
}
return sz[u];
}
void dfs3(int u, int tp) {
top[u] = tp;
dfn[u] = ++times;
if (!son[u]) {
return;
}
dfs3(son[u], tp);
for (pii p : T[u]) {
int v = p.fst;
if (!dfn[v]) {
dfs3(v, v);
}
}
}
int g[maxn][logn];
inline int qmax(int l, int r) {
if (l > r) {
return 0;
}
int k = __lg(r - l + 1);
return max(g[l][k], g[r - (1 << k) + 1][k]);
}
inline int trqmax(int x, int y) {
int res = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
res = max(res, qmax(dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
res = max(res, qmax(dfn[x] + 1, dfn[y]));
return res;
}
inline int query(int x, int u) {
int lst = st[x] - 1;
for (int v : gg[u]) {
if (st[x] <= st[v] && st[v] <= ed[x]) {
int l = lst + 1, r = st[v] - 1;
if (l <= r) {
if (find(rnk[r]) != find(u)) {
return rnk[r];
} else if (d[r] > l) {
return rnk[d[r] - 1];
}
}
lst = st[v];
}
}
if (lst + 1 <= ed[x]) {
int l = lst + 1, r = ed[x];
if (l <= r) {
if (find(rnk[r]) != find(u)) {
return rnk[r];
} else if (d[r] > l) {
return rnk[d[r] - 1];
}
}
}
return -1;
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n * 2; ++i) {
vector<int>().swap(G[i]);
vector<int>().swap(gg[i]);
vector<pii>().swap(T[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].d);
E[i].id = i;
gg[E[i].u].pb(E[i].v);
gg[E[i].v].pb(E[i].u);
}
sort(E + 1, E + m + 1, [&](const edg &a, const edg &b) {
return a.d < b.d;
});
for (int i = 1; i <= n * 2; ++i) {
ff[i] = i;
}
int ntot = n;
for (int i = 1; i <= m; ++i) {
int u = E[i].u, v = E[i].v, d = E[i].d;
int x = find(u), y = find(v);
if (x != y) {
int z = ++ntot;
ff[x] = ff[y] = z;
a[z] = d;
G[z].pb(x);
G[z].pb(y);
}
}
int rt = ntot;
dep[rt] = 1;
f[rt][0] = 0;
times = 0;
dfs(rt);
for (int i = 1; i <= n; ++i) {
ff[i] = i;
}
for (int j = 1; j <= 19; ++j) {
for (int i = 1; i <= n * 2 - 1; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
sort(gg[i].begin(), gg[i].end(), [&](const int &x, const int &y) {
return st[x] < st[y];
});
}
while (1) {
int cnt = 0;
for (int i = 1; i <= n; ++i) {
cnt += (ff[i] == i);
}
if (cnt == 1) {
break;
}
for (int i = 1; i <= n; ++i) {
c[i] = mkp(2e9, -1);
}
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && find(rnk[j + 1]) == find(rnk[i])) {
++j;
}
for (int k = i; k <= j; ++k) {
d[k] = i;
}
}
for (int u = 1; u <= n; ++u) {
int x = u;
for (int i = 19; ~i; --i) {
if (!f[x][i]) {
continue;
}
int v = f[x][i];
if (query(v, u) == -1) {
x = v;
}
}
x = f[x][0];
if (x) {
int t = query(x, u);
c[find(u)] = min(c[find(u)], make_pair(a[x], t));
}
}
for (int i = 1; i <= n; ++i) {
if (ff[i] == i) {
if (merge(i, c[i].scd)) {
T[i].pb(c[i].scd, c[i].fst);
T[c[i].scd].pb(i, c[i].fst);
}
}
}
}
times = 0;
for (int i = 1; i <= n; ++i) {
fa[i] = sz[i] = son[i] = dep[i] = top[i] = dfn[i] = 0;
}
dfs2(1, -1, 1);
dfs3(1, 1);
for (int i = 2; i <= n; ++i) {
g[dfn[i]][0] = b[i];
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
g[i][j] = max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 1; i <= m; ++i) {
int u = E[i].u, v = E[i].v;
ans[E[i].id] = trqmax(u, v);
}
for (int i = 1; i <= m; ++i) {
printf("%d ", ans[i]);
}
putchar('\n');
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}