目录
显示
题目链接
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; }