解题思路
货车所走的路径一定是最大生成树上的路径, 所以先跑一个最大生成树, 之后就是求一条路径上的最小值, 用树剖 + 线段树, 注意图可能不连通. 将边权下放到点权上, 但 x,y 路径上的 lca 的答案不能算, 因为他的点权来自上面的路径.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int MAXN = 50005;
- const int inf = 0x3f3f3f3f;
- inline int rd(){
- int x=0,f=1;char ch=getchar();
- while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
- while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
- return f?x:-x;
- }
- int n,m,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1],w[MAXN],Fa[MAXN],val[MAXN<<1];
- int fa[MAXN],dep[MAXN],id[MAXN],wt[MAXN],top[MAXN],siz[MAXN],son[MAXN];
- int Min[MAXN<<2],num,q;
- bool vis[MAXN];
- struct Node{
- int u,v,z;
- }node[MAXN];
- inline bool cmp(Node A,Node B){
- return A.z>B.z;
- }
- int get(int x){
- if(x==Fa[x]) return x;
- return Fa[x]=get(Fa[x]);
- }
- inline void add(int bg,int ed,int ww){
- to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=ww,head[bg]=cnt;
- }
- void dfs1(int x,int f,int d){
- fa[x]=f,dep[x]=d,siz[x]=1,vis[x]=1;
- int maxson=-1,u;
- for(register int i=head[x];i;i=nxt[i]){
- u=to[i];if(u==f) continue;
- w[u]=val[i];dfs1(u,x,d+1);
- siz[x]+=siz[u];
- if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}
- }
- }
- void dfs2(int x,int topf){
- id[x]=++num;wt[num]=w[x];top[x]=topf;
- if(!son[x]) return;
- dfs2(son[x],topf);int u;
- for(register int i=head[x];i;i=nxt[i]){
- u=to[i];if(u==fa[x] || u==son[x]) continue;
- dfs2(u,u);
- }
- }
- void build(int x,int l,int r){
- if(l==r) {
- Min[x]=wt[l];
- return;
- }
- int mid=(l+r)>>1;
- build(x<<1,l,mid),build(x<<1|1,mid+1,r);
- Min[x]=min(Min[x<<1],Min[x<<1|1]);
- }
- int query(int x,int l,int r,int L,int R){
- if(L<=l && r<=R) return Min[x];
- int mid=l+r>>1,ret=inf;
- if(L<=mid) ret=min(ret,query(x<<1,l,mid,L,R));
- if(mid<R) ret=min(ret,query(x<<1|1,mid+1,r,L,R));
- return ret;
- }
- int qRange(int x,int y){
- int u=get(x),v=get(y),ret=inf;
- if(u!=v) return -1;
- while(top[x]!=top[y]){
- if(dep[top[x]]<dep[top[y]]) swap(x,y);
- ret=min(ret,query(1,1,n,id[top[x]],id[x]));
- x=fa[top[x]];
- }
- if(x==y) return ret;
- if(dep[x]>dep[y]) swap(x,y);
- ret=min(ret,query(1,1,n,id[x]+1,id[y]));
- return ret;
- }
- int main(){
- n=rd(),m=rd();int x,y;
- for(int i=1;i<=n;i++) Fa[i]=i;
- for(int i=1;i<=m;i++) node[i].u=rd(),node[i].v=rd(),node[i].z=rd();
- sort(node+1,node+1+m,cmp);int uu,vv;
- for(int i=1;i<=m;i++){
- uu=get(node[i].u),vv=get(node[i].v);
- if(uu!=vv) {
- Fa[uu]=vv;
- add(node[i].u,node[i].v,node[i].z);
- add(node[i].v,node[i].u,node[i].z);
- }
- }
- for(int i=1;i<=n;i++)
- if(!vis[i]) {w[i]=inf;dfs1(i,0,1);dfs2(i,i);}
- q=rd();build(1,1,n);
- while(q--){
- x=rd(),y=rd();
- printf("%d\n",qRange(x,y));
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2784280.html