题解：CF2117G Omg Graph

_Missile_ · 2025-07-28 20:09:18 · 题解

题意

给定一张 n 个点 m 条边的无向连通带权图，请求出一条从节点 1 到节点 n 的路径（不一定是简单路径），设 k 为路径上经过的边的边权最小值加最大值，输出可能的 k 的最小值。

思路

先观察题目，发现题目要求的路径不一定是简单路径，因此我们可以想到，如果路径上的最大值固定，那么最小值越小越好。因此，我们可以按边权从小到大加入边，这样我们就可以认为节点 1 到节点 n 的所有路径上边权的最大值为当前加入的边的边权。为什么这样做是对的呢？因为我们是按边权从小到大加入边的，所以答案不会比正确答案算出来更优，而如果当前的边并不在节点 1 到节点 n 的任何一条路径上，那么真正的答案在这之前就已经算过了。不过我们在计算答案时我们需要判断一下节点 1 到节点 n 当前是否连通，如果不连通就不能计算答案。因此，我们就想到了并查集。现在只需要求出所有路径上的边权的最小值，也就是 1 节点能到达的边的边权最小值，而这也很好求，在维护并查集时再维护一个数组记录即可。

AC记录

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, m, fa[N], siz[N], op[N];

struct tp{
  int u, v, w;
};

vector<tp> v;

bool cmp(const tp &i, const tp &j){
  return i.w < j.w;
}

int Find(int x){
  return (fa[x] == x ? x : fa[x] = Find(fa[x]));
}

void Merge(int x, int y, int w){
  int fx = Find(x), fy = Find(y);
  if(fx != fy){
    if(siz[fx] < siz[fy]){
      swap(fx, fy);
    }
    fa[fy] = fx;
    siz[fx] += siz[fy];
    op[fx] = min({op[fx], op[fy], w});
  }
}
void solve(){
  cin >> n >> m;
  v.clear();
  for(int i = 1, u, V, w; i <= m; i++){
    cin >> u >> V >> w;
    v.push_back({u, V, w});
  }
  fill(siz + 1, siz + n + 1, 1);
  iota(fa + 1, fa + n + 1, 1);
  fill(op + 1, op + n + 1, 2e9 + 5);
  sort(v.begin(), v.end(), cmp);
  int ans = 2e9;
  for(tp it : v){
    Merge(it.u, it.v, it.w);
    if(Find(1) == Find(n)){
      ans = min(ans, it.w + op[Find(1)]);
    }
  }
  cout << ans << '\n';
}

int main(){
  ios::sync_with_stdio(false), cin.tie(0);
  int T;
  cin >> T;
  while(T--){
    solve();
  }
  return 0;
}