由于点数比较多，没法用邻接矩阵，所以不能用prim了 这里使用kruskal+LCA来找最大值
#include<iostream> #include<string> #include<cstdio> #include<set> #include<map> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; const int maxn = 50050,INF = 0x3f3f3f3f; int fa[maxn],n,m,dep[maxn],val[maxn],top[maxn]; bool vis[maxn]; struct Edge{ int to,from,val; bool operator < (const Edge &x) const{ return val < x.val; } }; vector<Edge> e; vector<pair<int,int>> tr[maxn]; int find(int x){ if (top[x] == x) return x; else return top[x] = find(top[x]); } void buildedge(Edge e){ int x = e.from,y = e.to,p = e.val; tr[x].push_back({y,p}); tr[y].push_back({x,p}); } void kruskal(){ int sum = 1,k = 0; for(int i = 1;i <= n;++i) top[i] = i; while(sum < n){ int x = find(e[k].from),y = find(e[k].to); if (x != y) { top[x] = y; buildedge(e[k]); sum++; } k++; } } void dfs(int u,int d){ dep[u] = d; vis[u] = true; for(int i = 0;i < tr[u].size();++i){ int p = tr[u][i].first,v = tr[u][i].second; if (!vis[p]){ val[p] = v; fa[p] = u; dfs(p,d+1); } } } void LCA(int x,int y){ int dx = dep[x],dy = dep[y]; int mi = 0; if (dx < dy){ swap(x,y); swap(dx,dy); } while(dx > dy){ mi = max(mi,val[x]); x = fa[x]; dx--; } while (x != y){ mi = max(mi,val[x]); x = fa[x]; mi = max(mi,val[y]); y = fa[y]; } cout << mi << endl; } void solve(){ int t,a,b; cin >> t; while(t--){ cin >> a >> b; LCA(a,b); } } void init(){ e.clear(); for(int i = 0;i < maxn;++i) tr[i].clear(); int a,b,p; for(int i = 0;i < m;++i){ cin >> a >> b >> p; e.push_back({a,b,p}); } sort(e.begin(),e.end()); kruskal(); memset(dep,0,sizeof dep); memset(vis,0,sizeof vis); memset(val,0,sizeof val); memset(fa,0,sizeof fa); dfs(1,0); solve(); } int main(){ int t = 0; while(cin >> n >> m){ if (t++) cout << endl; init(); } }