洛谷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][
32],m1[maxn][
32],h[maxn],dep[maxn];
//fa为kruscal的父亲数组 f为LCA的父亲数组
bool vis[maxn];
struct Node
{
int l;
int r;
int w;
}node[maxn*
5];
//原图的边
struct Edge
{
int nex;
int to;
int w;
}e[maxn*
5];
//重构树的边
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=
1;i<=
17;i++
)
{
for(
int j=
1;j<=n;j++
)
{
f[j][i]=f[f[j][i-
1]][i-
1];
m1[j][i]=min(m1[j][i-
1],m1[f[j][i-
1]][i-
1]);
//从儿子来取
}
}
}
int lca(
int x,
int y)
{
if(find(x)!=find(y))
return -
1;
//如果不在同一棵树中就不能到达
int ans=INF;
//初始化
if(dep[x]<
dep[y]) swap(x,y);
for(
int k=
17;k>=
0;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=
17;k>=
0;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][
0],m1[y][
0]));
//取父亲的最小值
return ans;
}
void dfs(
int u)
{
vis[u]=
1;
//判断已经在树中
for(
int i=h[u];i;i=
e[i].nex)
{
int v=
e[i].to;
if(vis[v])
continue;
//如果在树中就跳过
dep[v]=dep[u]+
1;
//记录深度
f[v][
0]=u;
//记录父亲
m1[v][
0]=e[i].w;
//初始化最小值为边权值
dfs(v);
}
return;
}
int main()
{
cin>>n>>
m;
for(
int i=
1;i<=n;i++) fa[i]=
i;
for(
int i=
1;i<=m;i++) cin>>node[i].l>>node[i].r>>
node[i].w;
sort(node+
1,node+
1+
m,cmp);
for(
int i=
1;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-
1)
break;
}
for(
int i=
1;i<=n;i++)
//预处理LCA
if(!vis[i])
//判断是不是同一棵树
{
dep[i]=
1;
//树根的深度为1
dfs(i);
f[i][0]=i;
//树根的父亲为自己
m1[i][
0]=INF;
//树根到父亲的最小值为一个极大值
}
pre();//预处理m1数组和f数组
cin>>
q;
for(
int i=
1;i<=q;i++
)
{
int x,y;
cin>>x>>
y;
cout<<lca(x,y)<<
endl;
}
}
转载于:https://www.cnblogs.com/BrokenString/p/9833246.html
