目录
显示
题目链接
https://www.luogu.org/problem/P1967
题解
方法一
直接采用 Floyd 计算显然是不现实的。
有一个显然的结论：图中的所有边中，决定答案的边并不算很多。比如连接两个相同城市的两条边，其中权值小的一条边显然是无用的。
那么我们只考虑能使图完全连通的权值较大的边，也就是构造最大生成树（因为图不保证联通，所以严格来说是最大生成森林）。从而将图的问题转变为较为容易维护的树上问题。
连接树上两点 \(x\) 和 \(y\) 的路径中的权值最小边可以划分成两个子问题：\(x\) 到 \(\text{lca}(x,y)\) 和 \(y\) 到 \(\text{lca}(x,y)\)。
考虑 dfs 时先倍增预处理当前点到祖先节点路径上的最小边权，再在 LCA 过程中利用预处理的数据把上面提到的两个子问题分开解决，最后合并两个子问题的解就是答案。
#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
int x,y,z;
}e1[50005];
struct edge
{
int v,w,next;
}e2[20005];
int f[10005],head[10005],vis[10005],fa[10005][25],dep[10005],dist[10005][25];
int cnt;
bool cmp(const node&a,const node&b)
{
return a.z>b.z;
}
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
void unionn(int x,int y)
{
f[x]=y;
}
void addedge(int u,int v,int w)
{
e2[++cnt].v=v;
e2[cnt].w=w;
e2[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int cur)
{
vis[cur]=1;
for(int i=head[cur];i;i=e2[i].next)
{
if(vis[e2[i].v])continue;
dep[e2[i].v]=dep[cur]+1;
fa[e2[i].v][0]=cur;
dist[e2[i].v][0]=e2[i].w;
dfs(e2[i].v);
}
return;
}
int query(int x,int y)
{
int ans=INF;
if(dep[x]>dep[y])swap(x,y);
for(int i=15;i>=0;i--)
if(dep[y]>=dep[x]+(1<<i))
{
ans=min(ans,dist[y][i]);
y=fa[y][i];
}
if(x==y)return ans;
for(int i=15;i>=0;i--)
if(fa[x][i]!=fa[y][i])
{
ans=min(ans,dist[x][i]);
x=fa[x][i];
ans=min(ans,dist[y][i]);
y=fa[y][i];
}
ans=min(ans,min(dist[x][0],dist[y][0]));
return ans;
}
int main()
{
int n,m,q;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e1[i].x,&e1[i].y,&e1[i].z);
for(int i=1;i<=n;i++)
f[i]=i;
sort(e1+1,e1+m+1,cmp);
for(int i=1;i<=m;i++)
if(find(e1[i].x)!=find(e1[i].y))
{
unionn(find(e1[i].x),find(e1[i].y));
addedge(e1[i].x,e1[i].y,e1[i].z);
addedge(e1[i].y,e1[i].x,e1[i].z);
}
for(int i=1;i<=n;i++)
if(!vis[i])
{
dep[i]=1;
dfs(i);
fa[i][0]=i;
dist[i][0]=INF;
}
for(int i=1;i<=15;i++)
for(int j=1;j<=n;j++)
{
fa[j][i]=fa[fa[j][i-1]][i-1];
dist[j][i]=min(dist[j][i-1],dist[fa[j][i-1]][i-1]);
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(find(x)!=find(y))puts("-1");
else printf("%dn",query(x,y));
}
return 0;
}
方法二
学了 Kruskal 重构树之后重新做了下这道题。
关于 Kruskal 重构树，可以看我写的 这篇文章。
按最大生成树建立 Kruskal 重构树（本题中是重构森林），则原图上 \(u,v\) 间最小边权的最大值就等于重构树上 \(\text{lca}(u,v)\) 的点权。
注意判断 \(u,v\) 不在同一集合的情况。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node
{
int u,v,w;
bool operator<(const node&a)const
{
return w>a.w;
}
}p[50005];
struct dsu
{
int fa[20005];
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void set(int x,int y)
{
fa[x]=y;
}
}d;
vector<int> e[20005];
int val[20005],fa[20005][25],dep[20005];
int n,m,cnt;
void build_retree()
{
sort(p+1,p+m+1);
cnt=n;
d.init(2*n);
for(int i=1;i<=m;i++)
{
int u=p[i].u,v=p[i].v;
int fu=d.find(u),fv=d.find(v);
if(fu!=fv)
{
cnt++;
e[cnt].push_back(fu);
e[cnt].push_back(fv);
d.set(fu,cnt),d.set(fv,cnt);
val[cnt]=p[i].w;
}
}
}
void dfs(int u,int f)
{
dep[u]=dep[f]+1,fa[u][0]=f;
for(int i=1;(1<<i)<=dep[u];i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto v:e[u])
dfs(v,u);
}
int lca(int x,int y)
{
if(dep[x]>dep[y])swap(x,y);
for(int i=20;i>=0;i--)
if(dep[y]-dep[x]>=(1<<i))
y=fa[y][i];
if(x==y)return x;
for(int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>p[i].u>>p[i].v>>p[i].w;
build_retree();
for(int i=1;i<=cnt;i++)
if(d.find(i)==i)dfs(i,0);
int q;
cin>>q;
while(q--)
{
int u,v;
cin>>u>>v;
if(d.find(u)!=d.find(v))cout<<-1<<endl;
else cout<<val[lca(u,v)]<<endl;
}
return 0;
}