当然这题有很多做法，但是我看到没有人写DSU的很惊奇
按照之前做连双向边题的经验，这题可以用并查集维护联通
然后对于每个询问\(x,y\)，考虑启发式合并
当两个点集\(x,y\)合并时，一些涉及到其中点的询问可以被解决，而遍历\(x,y\)中的询问集其实是等价的，所以可以直接用启发式合并存下这个点集涉及到的询问，在合并时我们要遍历数组，所以可以同时完成对于询问的回答
typedef long long ll; #define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i) #define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i) char IO; int rd(){ int s=0,f=0; while(!isdigit(IO=getchar())) if(IO=='-') f=1; do s=(s<<1)+(s<<3)+(IO^'0'); while(isdigit(IO=getchar())); return f?-s:s; } const int N=1e5+10; int n,m,q; struct Edge{ int u,v,x; void Get(){ u=rd(),v=rd(),x=rd(); } bool operator < (const Edge __) const { return x>__.x; } }e[N]; int ans[N]; struct Query{ int x,id; }; vector <Query> V[N]; int fa[N]; int Find(int x){ return fa[x]==x?x:fa[x]=Find(fa[x]);} int main(){ n=rd(),m=rd(); rep(i,1,n) fa[i]=i; rep(i,1,m) e[i].Get(); sort(e+1,e+m+1); rep(i,1,q=rd()) { ans[i]=-1; int x=rd(),y=rd(); V[x].push_back((Query){y,i}); V[y].push_back((Query){x,i}); } rep(i,1,m) { int x=Find(e[i].u),y=Find(e[i].v); if(x==y) continue; if(V[x].size()>V[y].size()) swap(x,y); fa[x]=y; rep(j,0,V[x].size()-1) { int t=V[x][j].x,id=V[x][j].id; if(Find(t)==y) { ans[id]=max(ans[id],e[i].x); } else V[y].push_back(V[x][j]); } } rep(i,1,q) printf("%d\n",ans[i]); }非常精简
如果你不懂启发式合并的原理，我可以简单证明一下
对于这些集合，元素总数为m
每一次我们将小的集合合并到大的上面，集合大小至少是两倍，所以每个元素最多会在log2(m)次合并中被访问到
总复杂度\(q \cdot log(q)\)
转载于:https://www.cnblogs.com/chasedeath/p/11332444.html
相关资源：JAVA上百实例源码以及开源项目