洛谷P1967：https://www.luogu.org/problemnew/show/P1967
思路
感觉2013年D1T3并不是非常难
但是蒟蒻还是WA了一次
从题目描述中看出每个点之间有许多条路径
而我们需要的是找出整条路径中最大的最小可通过量
一开始看到题目会想到是不是最大流问题 但是仔细一想其实并不用那么麻烦
我们只需要用kruscal找出最大生成树即可（因为多条路径中只要挑出最大的即可）
然后在重构树上考虑怎么取到两点之间的最小值
我们发现图是一个或者是多个树（没有考虑WA了一次）
所以我们可以用LCA代替朴素算法查找最小值 用一个m1[x][k]数组维护x到x的2k辈祖先路径中的最小值
这样题目就可以轻松A过
代码
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 10010
#define INF 100010
int n,m,q,k,cnt;
int fa[maxn],f[maxn][],m1[maxn][],h[maxn],dep[maxn];
//fa为kruscal的父亲数组 f为LCA的父亲数组
bool vis[maxn];
struct Node
{
int l;
int r;
int w;
}node[maxn*];//原图的边
struct Edge
{
int nex;
int to;
int w;
}e[maxn*];//重构树的边
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nex=h[u];
h[u]=cnt;
}
bool cmp(Node a,Node b)//从大到小
{
return a.w>b.w;
}
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
void pre()
{
for(int i=;i<=;i++)
{
for(int j=;j<=n;j++)
{
f[j][i]=f[f[j][i-]][i-];
m1[j][i]=min(m1[j][i-],m1[f[j][i-]][i-]);//从儿子来取
}
}
}
int lca(int x,int y)
{
if(find(x)!=find(y)) return -;//如果不在同一棵树中就不能到达
int ans=INF;//初始化
if(dep[x]<dep[y]) swap(x,y);
for(int k=;k>=;k--)
{
if(dep[f[x][k]]>=dep[y])
{
ans=min(ans,m1[x][k]);//取最小值
x=f[x][k];
}
if(x==y) return ans;
}
for(int k=;k>=;k--)
{
if(f[x][k]!=f[y][k])
{
ans=min(ans,min(m1[x][k],m1[y][k]));//取最小值
x=f[x][k];
y=f[y][k];
}
}
ans=min(ans,min(m1[x][],m1[y][]));//取父亲的最小值
return ans;
}
void dfs(int u)
{
vis[u]=;//判断已经在树中
for(int i=h[u];i;i=e[i].nex)
{
int v=e[i].to;
if(vis[v]) continue;//如果在树中就跳过
dep[v]=dep[u]+;//记录深度
f[v][]=u;//记录父亲
m1[v][]=e[i].w;//初始化最小值为边权值
dfs(v);
}
return;
}
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++) cin>>node[i].l>>node[i].r>>node[i].w;
sort(node+,node++m,cmp);
for(int i=;i<=m;i++)//kruscal
{
if(find(node[i].l)!=find(node[i].r))
{
fa[find(node[i].l)]=find(node[i].r);
add(node[i].l,node[i].r,node[i].w);//重构图
add(node[i].r,node[i].l,node[i].w);
k++;
}
if(k==n-) break;
}
for(int i=;i<=n;i++)//预处理LCA
if(!vis[i])//判断是不是同一棵树
{
dep[i]=;//树根的深度为1
dfs(i);
f[i][]=i;//树根的父亲为自己
m1[i][]=INF;//树根到父亲的最小值为一个极大值
}
pre();//预处理m1数组和f数组
cin>>q;
for(int i=;i<=q;i++)
{
int x,y;
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
}