前言
中文题目可以看 link 。
前置知识
简化题意
给定一个 \(N\) 个点 \(M\) 条边的有向图，共有 \(S\) 次询问，每次询问从 \(L\) 到 \(H\) 所有的路径中最小的权值的最大值（多组数据）。
- 本题即最大瓶颈路问题。
解法
使最小的权值最大，不难想到利用 Kruskal 重构树算法求解。
- 最小的权值最大的这个权值一定出现在原图的最大生成树上。
令 \(rt\) 表示原图的最大生成树的树根，\(dis_{i,j}\) 表示从 \(i\) 到 \(j\) 的路径上的最小值，不难得出 \(dis_{i,j}=\min(dis_{i,lca_(i,j)},dis_{j,lca(i,j)})\)。求任意两点的 LCA 可以用倍增或树剖等做法，此题使用倍增做法。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort stable_sort
#define endl '\n'
struct node
{
int nxt,from,to,w;
}e[700001],E[700001];
int head[700001],dep[700001],fminn[700001][25],fa[700001][25],f[700001],N,cnt=0;
bool cmp(node a,node b)
{
return a.w>b.w;
}
void add(int u,int v,int w)
{
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
int find(int x)
{
if(f[x]==x)
{
return x;
}
else
{
return f[x]=find(f[x]);
}
}
void kruskal(int m)
{
int i,x,y;
sort(E+1,E+1+m,cmp);
for(i=1;i<=m;i++)
{
x=find(E[i].from);
y=find(E[i].to);
if(x!=y)
{
f[x]=y;
add(E[i].from,E[i].to,E[i].w);
add(E[i].to,E[i].from,E[i].w);
}
}
}
void dfs(int x,int father,int w)
{
fa[x][0]=father;
dep[x]=dep[father]+1;
fminn[x][0]=w;
for(int i=1;(1<<i)<=dep[x];i++)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
fminn[x][i]=min(fminn[x][i-1],fminn[fa[x][i-1]][i-1]);
}
for(int i=head[x];i!=0;i=e[i].nxt)
{
if(e[i].to!=father)
{
dfs(e[i].to,x,e[i].w);
}
}
}
int lca(int x,int y)
{
if(find(x)!=find(y))
{
return -1;
}
else
{
int minn=0x7f7f7f7f;
if(dep[x]>dep[y])
{
swap(x,y);
}
for(int i=N;i>=0;i--)
{
if(dep[x]+(1<<i)<=dep[y])
{
minn=min(minn,fminn[y][i]);
y=fa[y][i];
}
}
if(x==y)
{
return minn;
}
else
{
for(int i=N;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
minn=min(minn,min(fminn[x][i],fminn[y][i]));
x=fa[x][i];
y=fa[y][i];
}
}
minn=min(minn,min(fminn[x][0],fminn[y][0]));
return minn;
}
}
}
int main()
{
int n,m,k,i,u,v,w,l,r;
while(cin>>n>>m>>k)
{
cnt=0;
memset(e,0,sizeof(e));
memset(E,0,sizeof(E));
memset(fa,0,sizeof(fa));
memset(dep,0,sizeof(dep));
memset(head,0,sizeof(head));
memset(fminn,0x3f,sizeof(fminn));
for(i=1;i<=n;i++)
{
f[i]=i;
}
for(i=1;i<=m;i++)
{
cin>>E[i].from>>E[i].to>>E[i].w;
}
kruskal(m);
N=log2(n)+1;
for(i=1;i<=n;i++)
{
if(dep[i]==0)
{
dfs(i,0,0x7f7f7f7f);
}
}
for(i=1;i<=k;i++)
{
cin>>l>>r;
cout<<lca(l,r)<<endl;
}
}
return 0;
}
后记
多倍经验：P1967 | P9235 | UVA12655 | P2245 |UVA11354 | AT_joisc2014_e
标签：cnt,Trucks,fa,int,题解,memset,700001,UVA12655,fminn From： https://www.cnblogs.com/The-Shadow-Dragon/p/17738796.html