[文章目录]
Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。
给出了一个无向图，问任意两点间路径上边权最小值最大的路径的最小边权。
kruskal+倍增
首先，想到只需要用尽量边权大的边将图联通就好了，所以kruskal求最大生成树。搜索处理一个森林中每一个点所属的树，该点的fa，与fa连的边的边权。最后倍增，将节点到2n级祖先边的边权最小值弄出来。查询时先判断所属的树，求LCA，两节点和LCA之间的最小边权倍增得出。
注意：如果LCA和一个节点重合，这个节点的最小边权需清成极大值。然后倍增维护时需要再找一下节点的len-2n级祖先（卡了好长时间）。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define M 51000
#define N 11000
int n,m,id,mx,t,c,k,dx,dy,q,ans1,ans2,num;
int v[N];
struct node
{
int v1,v2,date;
}a[M];
int f[N][20],dis[N][20],fa[N],deep[N],bin[50],Log[N];
int to[N<<1],head[N],nxt[N<<1],data[N<<1],cnt;
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
data[cnt]=z;
head[x]=cnt;
}
int find(int x)
{
return x==fa[x] ? x:fa[x]=find(fa[x]);
}
bool cmp(node x,node y)
{
return x.date>y.date;
}
void dfs(int x,int pre)
{
int i,y;
for(i=head[x];i;i=nxt[i])
{
y=to[i];
if(y==pre) continue;
v[y]=id;deep[y]=deep[x]+1;
f[y][0]=x;dis[y][0]=data[i];
dfs(y,x);
}
}
void getbin()
{
bin[0]=1;
for(int i=1;i<=mx;i++)
bin[i]=bin[i-1]<<1;
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
int i,tmp=deep[x]-deep[y];
for(i=0;bin[i]<=tmp;i++)
if(tmp&bin[i]) x=f[x][i];
if(x==y) return x;
for(i=mx;i>=0;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int ances(int x,int step)
{
int i;
for(i=0;bin[i]<=step;i++)
if(step&bin[i]) x=f[x][i];
return x;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;i++) fa[i]=i;
memset(dis,0x3f,sizeof(dis));
for(i=1;i<=m;i++)
scanf("%d%d%d",&a[i].v1,&a[i].v2,&a[i].date);
sort(a+1,a+m+1,cmp);
for(i=1;i<=m;i++)
{
dx=find(a[i].v1);
dy=find(a[i].v2);
if(dx!=dy)
{
num++;
fa[dx]=dy;
add(a[i].v1,a[i].v2,a[i].date);
add(a[i].v2,a[i].v1,a[i].date);
if(num==n-1)break;
}
}
for(i=1;i<=n;i++)
if(!v[i])
{
id++;v[i]=id;
dfs(i,0);
}
for(i=2;i<=n;i++)
Log[i]=Log[i>>1]+1;
mx=Log[n];
getbin();
for(i=1;i<=mx;i++)
for(j=1;j<=n;j++)
{
if(bin[i]<=deep[j])
{
f[j][i]=f[f[j][i-1]][i-1];
dis[j][i]=min(dis[f[j][i-1]][i-1],dis[j][i-1]);
}
}
scanf("%d",&q);
int x,y,tmp;
while(q--)
{
scanf("%d%d",&x,&y);
if(v[x]!=v[y])
{
printf("-1\n");
continue;
}
t=lca(x,y);
c=deep[x]-deep[t];
//printf("dis%d\n",c);
if(c!=0)
{
k=Log[c];
tmp=ances(x,c-bin[k]);
//printf("anc%d\n",tmp);
ans1=min(dis[x][k],dis[tmp][k]);
}
else ans1=1<<30;
c=deep[y]-deep[t];
//printf("dis%d\n",c);
if(c!=0)
{
k=Log[c];
tmp=ances(y,c-bin[k]);
//printf("anc%d\n",tmp);
ans2=min(dis[y][k],dis[tmp][k]);
}
else ans2=1<<30;
printf("%d\n",min(ans1,ans2));
}
return 0;
}