【算法】最大生成树+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
      
       #include
       
        #include
        
         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<
         
          <=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\n",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]
          
           =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\n",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\n",u,v,fa[5]);         if(getfa(u)!=getfa(v))          {              fa[fa[u]]=fa[v];//              printf("[]%d %d\n",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\n",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\n");         else printf("%d\n",ans);     }    return 0;}