哎就很惨，对着数据模拟改了半个小时后多拿了5分。
这道题要A是要log级别的算法的，这就让我想到了lca。
求路径最小值的最大值，那么那些小边如果不是没了就连不到某个点了是不是就不需要了啊？这样删一条边再删一条边就形成了一个最大生成树。
那么本题的思路最大生成树+lca就出现了。
先按照边权sort，然后跑克鲁斯卡尔最大生成树，用到的边都放在另一个邻接表里，其他的边全部扔掉。考虑到不一定只有一个树，就安安心心的跑完每一条边就好。
然后我们做lca和最小边的预处理。我喜欢的fa数组被并查集占用了，就用father凑合一下。lca的求法具体看我的上一篇呦。并且这道题要维护一个minn[i][k]表示从i向上走2^k的最小边。和fa数据转移相似：
对于边x,y,v: minn[y][0]=v; minn[y][k]=min(minn[y][k-1],minn[fa[y][k-1]][k-1]);
考虑到不一定只有一个树，我们对每个深度数组d[]没有被更新过的点都把它作为一个树的根节点做一遍预处理。
那么对于询问的时候，考虑到不一定在一个树里，要加上一句判断：
if(get(x)!=get(y)) return -1;
然后在x，y跳的时候跟着更新答案即可，在更新的时候要注意一起跳的时候如果有一个为0就不要更新了，否则一定会每个询问都输出0。
using namespace std; int i,tx,ty; int m,n,t; int fa[10010],father[10010][30],minn[10010][30],d[10010]; int link[10010]; int get(int x) { if(x==fa[x])return x; return fa[x]=get(fa[x]); } void hebing(int x,int y) { fa[get(x)]=get(y); } struct node { int x,y,v; int next; }o[100010],a[100010]; void add(int x,int y,int v) { t++; o[t].x=x; o[t].y=y; o[t].v=v; o[t].next=link[x]; link[x]=t; } bool Orz(node a,node y) { return a.v>y.v; } int minnn(int a,int b,int c) { if(b!=0) a=min(a,b); if(c!=0) a=min(a,c); return a; } void bfs(int now) { stack<int>q; q.push(now);d[now]=1; while(q.size()) { int x=q.top();q.pop(); for(int j=link[x];j!=0;j=o[j].next) { int y=o[j].y; if(d[y])continue; q.push(y); d[y]=d[x]+1; father[y][0]=x; minn[y][0]=o[j].v; for(int k=1;k<=t;k++) { father[y][k]=father[father[y][k-1]][k-1]; minn[y][k]=min(minn[y][k-1],minn[father[y][k-1]][k-1]); } } } } int ask(int x,int y) { if(get(x)!=get(y)) return -1; if(d[x]>d[y]) swap(x,y); int ans=200000; for(int k=20;k>=0;k--) if(d[father[y][k]]>=d[x]) { ans=min(ans,minn[y][k]); y=father[y][k]; } if(x==y)return ans; for(int k=20;k>=0;k--) if(father[x][k]!=father[y][k]) { ans=minnn(ans,minn[x][k],minn[y][k]); x=father[x][k],y=father[y][k]; } return minnn(ans,minn[x][0],minn[y][0]); } int main() { cin>>n>>m; for(i=1;i<=m;i++) cin>>a[i].x>>a[i].y>>a[i].v; for(i=1;i<=n;i++) fa[i]=i; sort(a+1,a+1+m,Orz); for(i=1;i<=m;i++) { if(get(a[i].x)!=get(a[i].y)) { hebing(a[i].x,a[i].y); add(a[i].x,a[i].y,a[i].v); add(a[i].y,a[i].x,a[i].v); } } t=(int)log(n*1.0)/log(2.0)+1; for(i=1;i<=n;i++) if(!d[i]) bfs(i); cin>>m; for(i=1;i<=m;i++) { cin>>tx>>ty; cout<<ask(tx,ty)<<endl; } }
还有一种克鲁斯卡尔重构树的算法我只得了60分,恳请改错: