P1967 [NOIP2013 提高组] 货车运输

Label

MST与LCA的简单应用

Description

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路$(u,v,w)$。每一条道路对车辆都有重量限制$w$，简称限重。现有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。如果货车不能到达目的地，输出$-1$。

数据范围： 1 ≤ n < 1 0 4 , 1 ≤ m < 5 × 1 0 4 , 1 ≤ q < 3 × 1 0 4 , 0 ≤ w ≤ 1 0 5 1\le n<10^4,1\leq m<5\times 10^4,1\leq q <3\times 10^4,0\leq w \leq 10^5 1≤n<104,1≤m<5×104,1≤q<3×104,0≤w≤105

Solution

我们首先考虑每辆货车经过的路径：由于司机一定会尽量避免走$w$小的路，那么对于每组询问，有一部分限重较小的边对答案无影响，算答案时不予考虑。故我们可得到如下猜想：司机所走的路径的每一条边都属于最大生成树的边集。

接下来考虑两点间路径最小边权的最大值：根据LCA的性质，树上两点到其LCA的路径$p$为两点间最短路径且对于两点间的任意路径$P$，必有$p\in P$。此时，对于每组询问，我们只需求出$p$上所有边的权值的最小值即可，这个最小值即为答案。

Summary

对于某些题，根据题目需要将数据进行处理从而去除无用信息、进而抽象出模型是一个思考题目的常规方法。

Code

#include
#include
#include
#define ri register int
using namespace std;const int MAXN=2e5+20,MI=15;
struct node{int U,V,W;
}E[MAXN];
bool cmp(const node &a,const node &b){return a.W > b.W;
}
int N,M,mtot,uni[MAXN],fau,fav,tot,u[MAXN],v[MAXN],w[MAXN],fst[MAXN],nxt[MAXN],Q,xi,yi;
int area[MAXN],connect,dep[MAXN],fa[MAXN][MI],f[MAXN][MI],ans;
bool vis[MAXN];int Find(int x)
{if(x==uni[x])	return x;return uni[x]=Find(uni[x]);
}void dfs(int x,int father,int depth,int ord,int Enum)
{vis[x]=true; area[x]=ord; dep[x]=depth;fa[x][0]=father; f[x][0]=w[Enum];for(ri k=1;(1<<k)<=dep[x];++k){fa[x][k]=fa[fa[x][k-1]][k-1];f[x][k]=min(f[x][k-1],f[fa[x][k-1]][k-1]);}for(ri k=fst[x];k>0;k=nxt[k])if(v[k]!=father)dfs(v[k],x,depth+1,ord,k);
}int Lca(int x,int y)
{if(dep[y]<dep[x])	swap(x,y);ans=MAXN;for(ri k=14;k>=0;--k)if(fa[y][k]!=0&&dep[fa[y][k]]>=dep[x]){ans=min(ans,f[y][k]);y=fa[y][k];}if(x==y)	return ans;for(ri k=14;k>=0;--k)if(fa[x][k]!=fa[y][k]){ans=min(ans,min(f[x][k],f[y][k]));x=fa[x][k]; y=fa[y][k];}ans=min(ans,min(f[x][0],f[y][0]));return ans;
}void Kruskal()
{sort(E+1,E+M+1,cmp);for(ri i=1;i<=N;++i)	uni[i]=i;for(ri i=1;i<=M;++i){fau=Find(E[i].U); fav=Find(E[i].V);if(fau!=fav){uni[fau]=fav; ++tot;u[++mtot]=E[i].U; v[mtot]=E[i].V; w[mtot]=E[i].W;nxt[mtot]=fst[u[mtot]]; fst[u[mtot]]=mtot;u[++mtot]=E[i].V; v[mtot]=E[i].U; w[mtot]=E[i].W;nxt[mtot]=fst[u[mtot]]; fst[u[mtot]]=mtot;} if(tot==N-1)	break;}	
}int main()
{scanf("%d%d",&N,&M);for(ri i=1;i<=M;++i) scanf("%d%d%d",&E[i].U,&E[i].V,&E[i].W);Kruskal();w[0]=MAXN;for(ri i=1;i<=N;++i)if(!vis[i])	dfs(i,0,0,++connect,0);scanf("%d",&Q);for(ri i=1;i<=Q;++i){scanf("%d%d",&xi,&yi);if(area[xi]!=area[yi])	cout<<"-1"<<'\n';else	cout<<Lca(xi,yi)<<'\n';}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！