Best Edge Weight

题目描述

You are given a connected weighted graph with $n$ vertices and $m$ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $i$. Let’s determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don’t change the other weights.

You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can’t be two edges with changed weights at the same time.

题意概述

给定一张$n$个点$m$条边的连通无向图，边权均为正数。对于每一条边，询问它的边权至多是多少，使得在其他边权不变的条件下，它在这张图的所有最小生成树中。

数据范围：$2 \le n \le 2 \times 10^5, \ n-1 \le m \le 2 \times 10^5$。

算法分析

题目要求一条边在所有最小生成树中。我们无法求出所有最小生成树，因此先求出其中一棵。这样，图中的边就被分成了两种：一种在这棵最小生成树中，另一种不在这棵最小生成树中。

对于不在这棵最小生成树中的边$(u, v)$，设它的权值为$w$。显然，它和最小生成树上从$u$到$v$的路径构成了一个环。设这条路径上边权的最大值$w_{max}$。如果$w \ge w_{max}$，那么$(u, v)$可能在这张图的一棵最小生成树中，但一定不是所有。因此，可以将$w$设成$w_{max}-1$，因为根据贪心策略，将路径上权值为$w_{max}$的边替换成$(u, v)$，会得到一棵更小的生成树。这种情况很好解决，只要在最小生成树上进行倍增就可以了。

对于在这棵最小生成树中的边$(u, v)$，设它的权值为$w$。假设我们找到了一条不经过这棵最小生成树上的边从$u$到$v$的路径，设这条路径上边权的最小值为$w_{min}$。类似于不在最小生成树的边，如果$w \ge w_{min}$，那么这条边一定不在所有最小生成树中。将它的权值设为$w_{min}-1$，即可满足要求。由于直接求$w_{min}$较为困难，因此可以按边权从小到大枚举不在这棵最小生成树中的边，并用它来更新最小生成树上的一条路径。因为是从小到大枚举，所以最小生成树上的每条边只需要被更新一次，可以用并查集维护。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct line {
  long long u, v, c, id; bool mst;
  bool operator < (const line &a) const { return c < a.c; }
} l[200001];
struct edge {
  long long v, c, id, nxt;
} e[400001];
long long n, m, nume, h[200001], fa[200001], ans[200001];
long long depth[200001], up[200001][20], ma[200001][20], uid[200001];
long long get_fa(long long t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void add_edge(long long u, long long v, long long c, long long id) {
  e[++nume].v = v, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa) {
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa) {
      depth[e[i].v] = depth[t] + 1, up[e[i].v][0] = t;
      ma[e[i].v][0] = e[i].c, uid[e[i].v] = e[i].id, dfs(e[i].v, t);
    }
}
long long get_max(long long u, long long v) {
  long long ret = 0;
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  for (int i = 19; i >= 0; --i)
    if (depth[u] - depth[v] >= (1 << i))
      ret = max(ret, ma[u][i]), u = up[u][i];
  if (u == v) return ret;
  for (int i = 19; i >= 0; --i)
    if (up[u][i] != up[v][i])
      ret = max(ret, max(ma[u][i], ma[v][i])), u = up[u][i], v = up[v][i];
  return max(ret, max(ma[u][0], ma[v][0]));
}
void update(long long u, long long v, long long val) {
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  long long p = u, q = v;
  for (int i = 19; i >= 0; --i)
    if (depth[p] - depth[q] >= (1 << i)) p = up[p][i];
  if (p != q) {
    for (int i = 19; i >= 0; --i)
      if (up[p][i] != up[q][i]) p = up[p][i], q = up[q][i];
    p = up[p][0];
  }
  u = get_fa(u), v = get_fa(v);
  while (depth[u] > depth[p])
    ans[uid[u]] = val - 1, q = get_fa(up[u][0]), fa[u] = q, u = get_fa(u);
  while (depth[v] > depth[p])
    ans[uid[v]] = val - 1, q = get_fa(up[v][0]), fa[v] = q, v = get_fa(v);
}
int main()
{
  cin >> n >> m, memset(ans, -1, sizeof ans);
  if (n == m + 1) {
    for (int i = 1; i <= m; cout << -1 << ' ', ++i); cout << endl; return 0;
  }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; cin >> l[i].u >> l[i].v >> l[i].c, l[i].id = i, ++i);
  sort(l + 1, l + m + 1);
  for (int i = 1; i <= m; ++i) {
    long long u = get_fa(l[i].u), v = get_fa(l[i].v);
    if (u != v) add_edge(l[i].u, l[i].v, l[i].c, l[i].id), fa[u] = v, l[i].mst = true;
  }
  depth[1] = 1, dfs(1, 0);
  for (int i = 1; i < 20; ++i)
    for (int j = 1; j <= n; ++j) {
      up[j][i] = up[up[j][i - 1]][i - 1];
      ma[j][i] = max(ma[j][i - 1], ma[up[j][i - 1]][i - 1]);
    }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; ++i)
    if (!l[i].mst) {
      ans[l[i].id] = get_max(l[i].u, l[i].v) - 1;
      update(l[i].u, l[i].v, l[i].c);
    }
  for (int i = 1; i <= m; cout << ans[i] << ' ', ++i);
  cout << endl;
  return 0;
}