【算法】最大生成树+LCA(倍增)
【题解】两点间选择一条路径最小值最大的路径，这条路径一定在最大生成树上，因为最大生成树就是从边权最大的边开始加的。
先求原图的最大生成树(森林)，重新构图，然后用一个超级根连向每棵树的根。
对于每个询问，在树上跑z=LCA(x,y)，答案就是x到z，z到y路上的最小值。
这个最小值可以在LCA(倍增)的过程中顺便维护(ms数组)，和祖先(倍增)数组的维护方式类似。
ms[e[x].to][0]=e[i].w;
ms[x][i]=min(ms[x][i-1],ms[f[x][i-1]][i-1]);
求ans的时候，x,y每次向上推进都求一次ans=min(ans,...)，具体可以看程序。
【注意】(只是提醒自己T_T)
1.每次要更新x,y的位置前先求ans。
2.无向边建两条，数组要开大，而且后面求生成树的时候要用建边总数而不是原边总数m！！！
3.超级根用0容易出错，用比maxn大的数字即可。
4.重新构图的新边表和旧边表各种变量注意区分
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f,maxn=10010; bool ok[maxn]; struct cyc{int next,from,to,w;}eo[150010],e[150010]; int cnt,tot,head[maxn],heads[maxn],fa[maxn],f[maxn][16],ms[maxn][16],vis[maxn],deep[maxn],n,m,q; void insert(int u,int v,int w) {cnt++;eo[cnt].from=u;eo[cnt].to=v;eo[cnt].w=w;eo[cnt].next=heads[u];heads[u]=cnt;} void ins(int u,int v,int w) {tot++;e[tot].from=u;e[tot].to=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot;} int getfa(int x) {return fa[x]==x?x:(fa[x]=getfa(fa[x]));} bool cmp(cyc a,cyc b) {return a.w>b.w;} void dfs(int x) { vis[x]=1; for(int i=1;(1<<i)<=deep[x];i++) f[x][i]=f[f[x][i-1]][i-1], ms[x][i]=min(ms[x][i-1],ms[f[x][i-1]][i-1]); // printf("head[%d]=%d",x,head[x]); for(int i=head[x];i;i=e[i].next){//printf("i=%d ",i); if(!vis[e[i].to]) { int now=e[i].to; deep[now]=deep[x]+1; f[now][0]=x; ms[now][0]=e[i].w; dfs(now); }} } int lca(int x,int y) { int ans=inf; if(deep[x]<deep[y])swap(x,y); int d=deep[x]-deep[y]; for(int i=0;(1<<i)<=d;i++) if((1<<i)&d)ans=min(ans,ms[x][i]),x=f[x][i]; // printf("lca=%d ",x); if(x==y)return ans; for(int i=15;i>=0;i--) if(f[x][i]!=f[y][i]) ans=min(ans,min(ms[x][i],ms[y][i])), x=f[x][i],y=f[y][i];//printf("lca=%d ",f[x][0]); if(f[x][0]==10010)return -1; return (ans=min(ans,min(ms[x][0],ms[y][0]))); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w); insert(v,u,w); } sort(eo+1,eo+cnt+1,cmp); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=cnt;i++) { int u=eo[i].from,v=eo[i].to; // printf("%d %d fa[5]=%d ",u,v,fa[5]); if(getfa(u)!=getfa(v)) { fa[fa[u]]=fa[v]; // printf("[]%d %d ",u,v); ins(u,v,eo[i].w); ins(v,u,eo[i].w); } } for(int i=1;i<=n;i++) if(!ok[getfa(i)])ok[fa[i]]=1,ins(10010,fa[i],inf); // for(int i=1;i<=tot;i++)printf("[]%d %d %d ",e[i].from,e[i].to,e[i].w); dfs(10010); scanf("%d",&q); for(int i=1;i<=q;i++) { int x,y; scanf("%d%d",&x,&y); int ans=lca(x,y); if(ans==-1)printf("-1 "); else printf("%d ",ans); } return 0; }