洛谷 P1967 [NOIP 2013 提高组] 货车运输 题解

原题链接：货车运输

kruskal重构树+LCA做法，树剖不想写
很容易发现原图跑最短路可以解，但是复杂度难以承受，所以考虑如何简化该图。
发现原图边权维护的应该是（u，v）的最小值，并且最优选择是这个最小值最大，所以如果有多条（u，v),只保留最大的没有影响，如果我们维护一棵最大生成树就一定包含（u，v）的最优解。这一部分可以用kruskal重构树。

然后考虑对于这棵树，如何求（u，v）路径上的最小值。
对于一棵树（u，v）是确定的唯一路径，我们可以发现可以把（u，v）拆成两条从LCA（u，v)到u和v的链，最后对它们取min。暴力的做法可以从u，分别上跳直到找到LCA（u，v），时间复杂度O（n），难以承受，所以用倍增LCA，同时维护一个数组st，st[i][j]表示i节点到i的2^j辈祖宗节点这条链的min，我们在求min（（i，LCA））时，发现可以通过类似LCA算法中将x，y深度拉平的方法，不断上跳使i逼近LCA，期间用每一条短链更新答案，最终求出min（（i，LCA）），最后合并两条链答案即可。时间复杂度O(nlogn)，可以接受。

AC代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int const N=1e4+10,M=5e4+10;
int p[N];
struct node{int u,v;int w;bool flag;
}tree[M];
int h[N],nx[M],to[M],vl[M],idx=1;
int n,m;
int deep[N],st[N][21],anst[N][21];bool cmp(node a,node b)
{return a.w>b.w;
}int find(int x)
{if(p[x]==x) return x;p[x]=find(p[x]);return p[x];
}void kruskal(){for(int i=1;i<=n;i++) p[i]=i;sort(tree+1,tree+m+1,cmp);for(int i=1;i<=m;i++){int u=tree[i].u,v=tree[i].v;int root1=find(u),root2=find(v);if(root1!=root2){p[root1]=root2;tree[i].flag=1;}}
}inline void add(int u,int v,int w)
{to[idx]=v;nx[idx]=h[u];vl[idx]=w;h[u]=idx++;
}void dfs(int u,int fa)
{if(u==0) anst[u][0]=0;else anst[u][0]=fa;if(u==0) deep[u]=0;else deep[u]=deep[fa]+1;for(int i=h[u];i;i=nx[i]){int v=to[i],w=vl[i];if(v==fa) continue;st[v][0]=w;dfs(v,u);}
}void first()
{for(int j=1;(1<<j)<=n;j++){for(int i=1;i<=n;i++){anst[i][j]=anst[anst[i][j-1]][j-1];}}
}int lca(int x,int y)
{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)x=anst[x][i];}if(x==y) return x;for(int i=20;i>=0;i--){if(anst[x][i]!=anst[y][i]){x=anst[x][i];y=anst[y][i];}if(anst[x][0]==anst[y][0]) break;}return anst[x][0];
}void RMQ()
{for(int j=1;(1<<j)<=n;j++){for(int i=1;i<=n;i++){st[i][j]=min(st[i][j-1],st[anst[i][j-1]][j-1]);}}
}int check(int fa,int v)
{int d=deep[v]-deep[fa];int mn=INT_MAX;for(int j=0;(1<<j)<=d;j++){if((1<<j) & d){mn=min(mn,st[v][j]);v=anst[v][j];}}return mn;
}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);tree[i].u=u;tree[i].v=v;tree[i].w=w;}kruskal();for(int i=1;i<=m;i++){if(!tree[i].flag) continue;int u=tree[i].u,v=tree[i].v,w=tree[i].w;add(u,v,w);add(v,u,w);}for(int i=1;i<=n;i++){if(p[i]==i) add(0,i,0);}dfs(0,-1);first();RMQ();int q;scanf("%d",&q);for(int i=1;i<=q;i++){int x,y;scanf("%d%d",&x,&y);int fa=lca(x,y);if(fa==0) cout<<-1<<endl;else printf("%d\n",min(check(fa,x),check(fa,y)));}return 0;
}