問題概要

無向グラフが与えられ、各辺には重みが付与されています。クエリでは2頂点間の経路における最小辺重みの最大値を求める必要があります。グラフは非連結の可能性があり、効率的な解法が求められます。

解法アプローチ

最適経路は最大ボトルネック生成木(MBST)上に存在します。MBSTはKruskal法を重み降順で適用して構築します。非連結グラフ対応のため、Union-Findで連結性を管理します。

経路クエリ処理には重軽分解を適用します。辺重みを深さの大きい方の頂点に割り当て、LCAの重みを除外するため区間クエリではid[x]+1から開始します。静的データのためST表で区間最小値を効率的に取得します。

実装例

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int MAX_NODES = 10005;
const int MAX_EDGES = 50005;

struct Edge {
  int src, dest, weight;
};

struct UnionFind {
  vector<int> parent;
  UnionFind(int n) : parent(n+1) {
    for(int i = 1; i <= n; i++) parent[i] = i;
  }
  int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
  }
  void unite(int x, int y) {
    parent[find(x)] = find(y);
  }
  bool connected(int x, int y) {
    return find(x) == find(y);
  }
};

struct Graph {
  vector<vector<pair<int, int>>> adj;
  Graph(int n) : adj(n+1) {}
  void addEdge(int u, int v, int w) {
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
};

struct HLD {
  vector<int> parent, depth, heavy, head, pos, treeWeight;
  vector<vector<int>> stTable;
  int curPos = 0;

  void init(int n) {
    parent.resize(n+1);
    depth.resize(n+1);
    heavy.resize(n+1, -1);
    head.resize(n+1);
    pos.resize(n+1);
    treeWeight.resize(n+1);
  }

  int dfsInit(Graph &g, int node) {
    int size = 1, maxChild = 0;
    for(auto &edge : g.adj[node]) {
      int child = edge.first;
      if(child == parent[node]) continue;
      parent[child] = node;
      depth[child] = depth[node] + 1;
      int childSize = dfsInit(g, child);
      size += childSize;
      if(childSize > maxChild) {
        maxChild = childSize;
        heavy[node] = child;
      }
    }
    return size;
  }

  void decompose(Graph &g, int node, int h) {
    head[node] = h;
    pos[node] = curPos++;
    if(heavy[node] != -1) {
      decompose(g, heavy[node], h);
    }
    for(auto &edge : g.adj[node]) {
      int child = edge.first;
      if(child != parent[node] && child != heavy[node]) {
        decompose(g, child, child);
      }
    }
  }

  void buildST() {
    int n = curPos;
    int logLevel = 0;
    while((1 << logLevel) <= n) logLevel++;
    stTable = vector<vector<int>>(logLevel, vector<int>(n));

    for(int i = 0; i < n; i++) {
      stTable[0][i] = treeWeight[i];
    }

    for(int level = 1; level < logLevel; level++) {
      for(int i = 0; i + (1 << level) <= n; i++) {
        stTable[level][i] = min(stTable[level-1][i], stTable[level-1][i + (1 << (level-1))]);
      }
    }
  }

  int stQuery(int l, int r) {
    if(l > r) return 1e9;
    int len = r - l + 1;
    int level = 0;
    while((1 << (level+1)) <= len) level++;
    return min(stTable[level][l], stTable[level][r - (1 << level) + 1]);
  }

  int pathQuery(UnionFind &uf, int u, int v) {
    if(!uf.connected(u, v)) return -1;
    int result = 1e9;
    while(head[u] != head[v]) {
      if(depth[head[u]] < depth[head[v]]) swap(u, v);
      result = min(result, stQuery(pos[head[u]], pos[u]));
      u = parent[head[u]];
    }
    if(depth[u] > depth[v]) swap(u, v);
    if(u != v) {
      result = min(result, stQuery(pos[u] + 1, pos[v]));
    }
    return result;
  }
};

int main() {
  int nodeCount, edgeCount;
  cin >> nodeCount >> edgeCount;
  
  vector<Edge> edges(edgeCount);
  for(int i = 0; i < edgeCount; i++) {
    cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
  }
  
  sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
    return a.weight > b.weight;
  });
  
  UnionFind uf(nodeCount);
  Graph mstGraph(nodeCount);
  
  for(auto &e : edges) {
    if(!uf.connected(e.src, e.dest)) {
      uf.unite(e.src, e.dest);
      mstGraph.addEdge(e.src, e.dest, e.weight);
    }
  }
  
  HLD hld;
  hld.init(nodeCount);
  
  for(int i = 1; i <= nodeCount; i++) {
    if(hld.depth[i] == 0) {
      hld.depth[i] = 1;
      hld.dfsInit(mstGraph, i);
    }
  }
  
  for(int i = 1; i <= nodeCount; i++) {
    for(auto &edge : mstGraph.adj[i]) {
      int neighbor = edge.first;
      if(hld.depth[i] > hld.depth[neighbor]) {
        hld.treeWeight[hld.curPos] = edge.second;
      }
    }
  }
  
  hld.curPos = 0;
  for(int i = 1; i <= nodeCount; i++) {
    if(hld.head[i] == 0) {
      hld.decompose(mstGraph, i, i);
    }
  }
  
  hld.buildST();
  
  int queryCount;
  cin >> queryCount;
  while(queryCount--) {
    int u, v;
    cin >> u >> v;
    cout << hld.pathQuery(uf, u, v) << '\n';
  }
  
  return 0;
}