[洛谷 1967][NOIP2013]货车运输

题目链接

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据