首先题目要求路径中的最大的最小值 所以建立最大生成图那么唯一路径中的最小值就是题目答案又因为如果使用dfs/bfs求最小值的话 时间复杂度是 O(n * q) 会超时 所以使用lca（最近公共祖先）的思路求路径最小值。不了解的话建议在ACwing 上y总在提高课中有讲到（安利一波）或者阅读：https://blog.csdn.net/jeryjeryjery/article/details/52853017我们在裸的模板 上还要在维护 wmin 数组 （wmin[a][i] 表示a点向上找2^i个祖先的最短边）建议lca建树的dfs 写成bfs 因为dfs有爆栈的风险。代码如下： #inclu...

水题 直接kruskal 加边数 == p - s 返回边长即可代码如下 #include<bits/stdc++.h> using namespace std; const int N = 510; int s, p; struct edge{ int a, b; double c; bool operator<(const edge & w)const{ return c < w.c; } }edges[N * N];//完全图 struct node{ int x, y; }node[N]; ...

洛谷题单<最小生成树> 2krukal 的应用 题目告诉原有M条边 即修改M次并查集；考察对kruskal并查集的理解。代码如下 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1010, M = 1010; struct edge{ int a, b; double c; bool operator<(const edge& w){ return c < w.c; } }edges[N*N...

洛谷题单<最小生成树> 直接上代码 #include<bits/stdc++.h> using namespace std;//prim kruskal 都可以做； const int N = 5010, M = 200010; struct edge{ int a, b, c; bool operator<(const edge& w)const{ return c < w.c; } }edges[M]; int n, m, p[N], cnt; //并查集； int find(int x){//...